I use these notations: fix $n\in \mathbb{N}$, a (realisation of a random) graph is a pair $([n],E_n)$, where $[n]=\{1,\dots,n\}$ and $E_n$ is the (directed) edge set, which means that vertex $i$ is connected to vertex $j$ if and only if the pair $(i,j)$ is in $E_n$.
In particular $E_n \subset [n]\times[n]$ and, since I'm assuming the graph to be a directed graph, $(i,j)\in E_n$ does not imply $(j,i) \in E_n$.
Let $X_{ij}$ denote the random variable associated to the edge $(i,j)$: it takes value 1 if $(i,j)\in E_n$ and 0 otherwise.
Given a random graph, I'm interested in the edge correlation, which means that I want to understand the quantity: $$ Cov(X_{ij},X_{kl})=\mathbb{E}[X_{ij}X_{kl}]-\mathbb{E}[X_{ij}]\mathbb{E}[X_{kl}], $$ as a function of the size of the system $n$. Basically, I would like an upper-bound such as $Cov(X_{ij},X_{kl})\leq \tfrac{1}{n^{\alpha}}$ for some $\alpha >0$.
It's clear that if one takes any Erdős-Rényi $ER(n,p_n)$ random graph the correlation is zero because of the independence between the edges (for every $n$ and every sequence of $p_n$). But
- Q1 what if one take the $d$-uniform random graph (for different behaviors of $d$ w.r.t. $n$)?
- Q2 Is there a "simple" way to compute the covariance for, let's say, the configuration model ^?
- Q3 Do large deviations exist for this problem?
I imagine the correlation to be large for scale free random graphs and small for uniform/dense graphs (such as $ER$...), but I couldn't find anything about.
^ I'm following the definition in Van der Hofstadt's book.
PS Is it maybe a MathOverflow question?
Let's use configurations. Let $i,j,k,l$ be vertices, and let $E(u)$ denote the set of half-edges glued to vertex $u$ (hence $|E(u)| = \mathrm{deg}(u)$. Computing the covariance between the edges $(i,j)$ and $(k,l)$ is straighforward using the configuration model, because $X_{i,j}$ is equal to $$\sum_{e \in E(i), f \in E(j)} \mathbf 1_{e \to f}$$ hence we have $$\mathbf{E}[X_{i,j}X_{k,l}] = \sum_{e,f,g,h}\mathbf{P}(e\to f, g\to h)$$ where the sum is taken on $4$-tuples $e\in E(i), f\in E(j), g\in E(k), h \in E(l)$. If the 4 vertices are distinct then $\mathbf{P}(e \to f, g \to h)$ is equal to $\frac{1}{(m-1)(m-3)}$ where $m$ is the total number of half-edges. In the end you get something like $$\mathbf{E}[X_{i,j}X_{k,l}] = \frac{d_i d_j d_k d_l}{(m-1)(m-3)}.$$
When $i,j,k,l$ are not distinct the same kind of computations work.