Sparsity of the covariance matrix for uniformly random DAGs

About 14 years old · traced to 2012

Let $G=(V,A)$ be a directed acyclic graph, and let $\Sigma$ denote the covariance matrix of its arc-indicator variables. Covariance-matrix sparsity conjecture. The covariance matrix $\Sigma$ is sparse. The proportion of pairs of arcs incident on a common node tends to zero as the number of nodes tends to infinity; conditional on the preceding uncorrelatedness conjecture, this would imply that the proportion of zero entries of $\Sigma$ tends to one. The claim is motivated by enumeration and asymptotic counting, but remains unproved.

References

Primary source

Marco Scutari, “On the Prior and Posterior Distributions Used in Graphical Modelling”, arXiv:1201.4058 (2012).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

The claim that random directed acyclic graphs have mostly zero covariance entries remains unverified; a reader-written symmetry argument claims a complete proof.

Scutari’s paper formulates the covariance-matrix sparsity conjecture for uniformly random directed acyclic graphs and records it as unproved. The conjecture predicts that almost all covariance entries vanish asymptotically.

Posted attempt

A reader-written argument claims a complete proof by replacing arc indicators with signed variables $X_{ij}$ and using vertex-exchange symmetry: covariances for disjoint endpoint pairs cancel exactly. It derives at most $O(n^3)$ potentially nonzero entries among $\Theta(n^4)$ entries, but the argument has not been independently verified.

Current status (as of August 2026): The conjecture is recorded as unproved in the primary source, while a complete proof has been claimed in an unverified reader-written argument; no independent confirmation was found.

Sources

arxiv.org

ProofThis solution needs a summarySee full solutionHide full solution

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.