Uncorrelatedness of nonincident arcs in uniformly random DAGs
Let be a directed acyclic graph, with arcs represented by indicator random variables and covariance matrix . 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 , . This is supported by complete enumerations through seven nodes and simulations for larger DAGs, but no formal proof is given.
References
- Marco Scutari, “On the Prior and Posterior Distributions Used in Graphical Modelling”, arXiv:1201.4058 (2012).
Progress summary
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 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 under vertex-exchangeability, and claims a stronger covariance classification. It does not establish the Boolean-indicator conjecture, because swapping endpoints changes to but does not turn the indicator 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
Solutions 1
This solution needs a summarySee 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
Let be uniformly distributed over all labeled directed acyclic graphs on . More generally, the following proof applies to every vertex-exchangeable distribution on directed graphs with no oppositely oriented parallel arcs.
For any distinct , the vertex transposition preserves the distribution and satisfies
Consequently . If are distinct, the same transposition fixes . Therefore
and hence
This proves Conjecture 3.1 for every ; neither acyclicity nor uniformity is needed beyond vertex-exchangeability.
A stronger classification follows. Write , , , and let be the oriented vertex-edge incidence matrix of the complete graph. Exchangeability and the vanishing just proved give
Since , the two covariance eigenvalues are , with multiplicity , and , with multiplicity .
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.