Sparsity of the covariance matrix for uniformly random DAGs

Use the signed arc variables from equation (4) of the primary source:

$$X_{ij}= \begin{cases} 1,&i\to j,\\ -1,&j\to i,\\ 0,&\text{neither arc is present}, \end{cases} \qquad X_{ji}=-X_{ij}.$$

The uniform distribution on labeled directed acyclic graphs is invariant under vertex relabeling. The vertex transposition $(ij)$ changes the sign of $X_{ij}$; if $\{i,j\}\cap\{k,l\}=\varnothing$, it leaves $X_{kl}$ unchanged. Therefore

$$\mathbb E X_{ij}=0,\qquad \mathbb E[X_{ij}X_{kl}] =-\mathbb E[X_{ij}X_{kl}]=0,$$

and every covariance between disjoint arcs vanishes exactly.

Index the covariance matrix by the $M=\binom n2$ unordered vertex pairs, choosing one orientation for each pair. For each row, exactly $\binom{n-2}{2}$ column pairs have disjoint endpoints and therefore contain zeros. Hence

$$\#\{(e,f):\Sigma_{ef}=0\} \ge M\binom{n-2}{2}$$

and

$$\boxed{ \frac{\#\{(e,f):\Sigma_{ef}=0\}}{M^2} \ge \frac{\binom{n-2}{2}}{\binom n2} = \frac{(n-2)(n-3)}{n(n-1)} \longrightarrow1. }$$

Equivalently, each row contains at most $2n-3$ potentially nonzero entries. Thus the entire covariance matrix has at most $\binom n2(2n-3)=O(n^3)$ nonzero entries among its $\binom n2^2=\Theta(n^4)$ entries.

This proves Conjecture 3.2 quantitatively. The argument in fact applies to every vertex-exchangeable distribution on directed graphs with no oppositely oriented parallel arcs.

Source: M. Scutari, “On the Prior and Posterior Distributions Used in Graphical Modelling,” Bayesian Analysis 8 (2013), 505–532, equation (4) and Conjectures 3.1–3.2, doi:10.1214/13-BA819.