Uncorrelatedness of nonincident arcs in uniformly random DAGs

At least 13 years old · documented by 2012

Let $G=(V,A)$ be a directed acyclic graph, with arcs represented by indicator random variables $A_{ij}$ and covariance matrix $\Sigma$ . Two arcs are incident when they share a common node. Uncorrelatedness conjecture. Arcs that are not incident on a common node are uncorrelated; equivalently, for distinct nodes $i,j,k,l$ , $\mathsf{COV}(A_{ij},A_{kl})=0$ . This is supported by complete enumerations through seven nodes and simulations for larger DAGs, but no formal proof is given.

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

Open

A posted symmetry argument proves a related statement for signed edge variables, not for the Boolean indicators here, so the conjecture remains open.

Scutari’s 2013 work formulates the conjecture that nonincident arcs in a uniformly random labeled directed acyclic graph have zero covariance. The conjecture concerns Boolean arc-presence indicators and has not received a verified proof.

Known results

Scutari, 2013: complete enumeration through $7$ vertices supports the conjecture.
Scutari, 2013: simulations for larger graphs also support it.

Posted attempt

A proposed transposition argument gives zero covariance for signed trinomial variables $X_{ij}\in\{-1,0,1\}$ under vertex-exchangeability, and claims a stronger covariance classification. It does not establish the Boolean-indicator conjecture, because swapping endpoints changes $X_{ij}$ to $-X_{ij}$ but does not turn the indicator $A_{ij}$ into its negative; the attempt has not been independently verified.

Current status (as of August 2026): the Boolean-indicator conjecture remains open; the posted proof attempt addresses a different signed-variable statement and provides no verified progress on the target claim.

Sources

arxiv.org

ProofThis solution needs a summarySee full solutionHide full solution

The primary source's arc variables are signed trinomial variables, not Boolean edge-presence indicators. In the notation of its equation (4), set

X_{ij}(G)= \begin{cases} 1,&i\to j\text{ belongs to }G,\\ -1,&j\to i\text{ belongs to }G,\\ 0,&\text{neither arc belongs to }G, \end{cases} \qquad X_{ji}=-X_{ij}.

Let $G$ be uniformly distributed over all labeled directed acyclic graphs on $[n]$ . More generally, the following proof applies to every vertex-exchangeable distribution on directed graphs with no oppositely oriented parallel arcs.

For any distinct $i,j$ , the vertex transposition $\tau=(ij)$ preserves the distribution and satisfies

X_{ij}(\tau G)=-X_{ij}(G).

Consequently $\mathbb E X_{ij}=0$ . If $i,j,k,l$ are distinct, the same transposition fixes $X_{kl}$ . Therefore

\mathbb E[X_{ij}X_{kl}] =\mathbb E[X_{ij}(\tau G)X_{kl}(\tau G)] =-\mathbb E[X_{ij}X_{kl}],

and hence

\boxed{\operatorname{Cov}(X_{ij},X_{kl})=0.}

This proves Conjecture 3.1 for every $n$ ; neither acyclicity nor uniformity is needed beyond vertex-exchangeability.

A stronger classification follows. Write $M=\binom n2$ , $v=\mathbb E X_{12}^{2}$ , $c=\mathbb E[X_{12}X_{13}]$ , and let $B$ be the oriented vertex-edge incidence matrix of the complete graph. Exchangeability and the vanishing just proved give

\Sigma=(v-2c)I_M+cB^{\mathsf T}B.

Since $BB^{\mathsf T}=nI_n-\mathbf1\mathbf1^{\mathsf T}$ , the two covariance eigenvalues are $v+(n-2)c$ , with multiplicity $n-1$ , and $v-2c$ , with multiplicity $M-n+1$ .

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