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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.