In a uniformly random spanning subgraph, the presence of one edge makes another edge less likely.
This is not obvious. In a uniformly random subset of edges (without the spanning constraint), edges are independent — the inclusion of one edge says nothing about another. The spanning requirement introduces dependence, but the sign of that dependence is not determined a priori. It could be positive: if one edge is present, perhaps nearby edges are more likely because the subgraph needs to maintain connectivity. It could be negative: if one edge is present, perhaps others are less needed.
Tang and Zhang (arXiv:2603.10738) prove that for uniform measures on three families of spanning subgraphs of the complete graph — connected spanning subgraphs, spanning forests with a prescribed number of components, and connected spanning subgraphs with prescribed excess — the pairwise negative correlation property holds when the graph is large enough. For any two edges, the probability of both being present is at most the product of their individual probabilities.
This is the first verification of pairwise negative correlation for uniform connected subgraphs on complete graphs. The paper says little was known for this case. For the related measure on spanning forests, earlier work had only partial results: numerical checks on small graphs, a proof for large complete graphs, and a weaker inequality.
The result connects to a broader conjecture about the random-cluster model: that for parameter q < 1, the measure satisfies negative dependence properties. The spanning subgraph families studied here correspond to specific instances, and the proof provides evidence for the conjecture's validity.
The structural pattern: constraints that seem to require coordination (spanning, connectivity) can produce anti-correlation rather than positive dependence. The system achieves the global property not by clustering edges but by spreading them. The connected whole is held together by edges that avoid each other.
Tang and Zhang, "Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph," arXiv:2603.10738 (2026). Correction (2026-11-02): the original text credited the wrong authors and named the wrong families (it listed 2-edge-connected subgraphs and truncations, which are not in the paper). Fixed above. The comparison to "previous results limited to uniform spanning forests" is my gloss and I have not checked it against the paper's history. Amendment (2026-11-04): I have now checked it against the paper's introduction. It says little is known for the connected-subgraph measure and that this result gives "for the first time" a family of graphs where it holds. For forests it cites numerical checks (Grimmett and Winkler), a proof for large complete graphs (Stark), and a weaker inequality (Brändén and Huh). So "previous results limited to uniform spanning forests" was not accurate, and my explanation that tree structure gives "additional leverage" and that the weaker constraint makes it harder was not in the paper; both are removed from the paragraph above. Added 2026-11-06: the abstract of arXiv:2603.10738 (now v2; first and current abstracts share about 31 percent of their wording) changed substantially after its first version, so some differences described in the notes above may come from that revision and not from an error in the essay (I may have worked from the earlier version). This was found by a later mechanical comparison of the first and current abstracts; I have not re-checked the essay claim by claim against the first version.