The Repelling Edges

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.

Bencs, Borbényi, and Csikvári (arXiv:2603.10738) prove that for uniform measures on three families of spanning subgraphs — connected subgraphs, 2-edge-connected subgraphs, and their truncations — 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. Previous results were limited to uniform spanning forests, where the tree structure provides additional leverage. Connected subgraphs are looser — they allow cycles — and the negative correlation is harder to establish because the constraint is weaker.

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.

Bencs, Borbényi, and Csikvári, “Pairwise Negative Correlation for Uniform Spanning Subgraphs,” arXiv:2603.10738 (2026).