Edges that crowd each other out

Drawn without putting back found that the draws of a sample taken without replacement are dependent, and that the dependence helps. Every ball taken from an urn makes the next ball of the same colour less likely, the indicators are negatively associated, and Chernoff’s bounds apply as if the draws were independent — or better. It closed by naming the question this property raises. Which random structures have it? A uniformly random spanning tree of a graph does, by a theorem. A uniformly random spanning forest, the same object with one constraint removed, is conjectured to, and the conjecture has been open for twenty years.

The question is concrete and finite in each case. For a given graph and two of its edges, count the forests that contain neither, one or both, and check one inequality between whole numbers. Every graph small enough to enumerate can be checked exactly, and this essay does that for every labelled graph up to six vertices. It does the same for spanning trees, where the inequality is a theorem, for connected spanning subgraphs, where it is another conjecture, and for matchings, where it is false.

The inequality to check #

Choose a structure uniformly at random from some family of edge sets — all spanning trees of a graph, say. For two edges $e$ and $f$, write $N$ for the number of structures in the family, $N_e$ and $N_f$ for those containing each edge, and $N_{ef}$ for those containing both. The edges are negatively correlated when

$$\Pr(e \text{ and } f) \le \Pr(e)\Pr(f), \qquad\text{that is,}\qquad N \cdot N_{ef} \le N_e \cdot N_f.$$

The ratio $N N_{ef}/(N_e N_f)$ is one exactly when the two edges are independent, below one when knowing that $e$ is present makes $f$ less likely, and above one when it makes $f$ more likely.

For the square with a diagonal in the hero figure, the two marked sides lie in 5 of the 8 spanning trees each and together in 3, so the ratio is $8 \times 3/(5 \times 5) = 0.96$. For forests — any set of edges containing no cycle, whether or not it connects everything — the counts are 24 forests, 10 with each edge and 4 with both, and the ratio is again $0.96$. For connected subgraphs, edge sets that reach every vertex, it is $0.98$. All three families make the two edges mildly repel each other.

The triangle and the square by hand #

The smallest cases can be counted on the fingers, and they already show the pattern. A triangle has three edges and $2^3 = 8$ edge sets. Every set except all three is a forest, so there are 7: the empty set, three single edges, and three pairs. A given edge lies in 3 of them and two given edges together in 1, so the ratio is $7 \times 1/(3 \times 3) = 7/9 \approx 0.778$. That is the census’s tightest value for three vertices, since the triangle is the only graph on three vertices with no cut vertex. The triangle’s spanning trees are its three pairs of edges, each edge in two of them and two edges together in one, for a ratio of $3 \times 1/(2 \times 2) = 0.75$.

A four-cycle has 16 edge sets and every one except the whole cycle is a forest: 15 forests. An edge lies in $2^3 - 1 = 7$ of them, two edges together in $2^2 - 1 = 3$, so the ratio is $15 \times 3/49 \approx 0.918$. Its spanning trees are the four ways of deleting one edge. Each edge is in 3 and two edges together in 2, for $4 \times 2/9 \approx 0.889$. In both shapes the trees repel more strongly than the forests, the pattern the distribution figure shows on six vertices. In both, the only thing stopping an edge set from being a forest is the single cycle, and the cycle is what links the edges’ fates — in a general graph, every cycle of its cycle space plays that part at once.

For a single cycle of length $k$ the forest ratio is $(2^k - 1)(2^{k-2} - 1)/(2^{k-1} - 1)^2$, which rises towards one as $k$ grows — a long cycle constrains each pair of its edges only weakly. That is the first hint of why the closest calls in larger graphs come so near to independence: they are pairs whose only interactions run round long cycles.

Why trees repel: Kirchhoff’s resistances #

For spanning trees the inequality is a theorem, and its proof is a piece of nineteenth-century electricity. Gustav Kirchhoff showed in 1847 that the number of spanning trees of a graph is a determinant, the result a determinant that counts trees drew. The same work gives a probability. Treat each edge as a resistor of one ohm. Then the chance that a uniform spanning tree contains the edge $e$ equals the effective resistance between its endpoints — the voltage needed to push one unit of current from one end to the other through the whole network.

Conditioning on $e$ being in the tree is the same as contracting $e$, merging its two endpoints into one. Contracting an edge is like replacing a resistor by a wire, and Rayleigh’s monotonicity principle says that lowering any resistance in a network can only lower every effective resistance. So after the contraction, the effective resistance across $f$ is no larger, and the chance that $f$ is in the tree is no larger. That is negative correlation, for every graph and every pair of edges, proved in four sentences.

The proof also says when the inequality is an equality. If contracting $e$ leaves the resistance across $f$ unchanged, the two edges are exactly independent. That happens in the complete graph on four vertices for two opposite edges. It is the balanced Wheatstone bridge, in which no current flows across the bridge edge, so shorting it changes nothing. Of the 16 spanning trees of $K_4$, each edge is in 8, and two opposite edges are together in 4, giving a ratio of exactly $16 \times 4/(8 \times 8) = 1$. The census below finds this case on its own.

Tomás Feder and Milena Mihail proved the stronger property, negative association, for spanning trees in 1992. Any increasing function of some edges’ indicators and any increasing function of the others are negatively correlated. That is what brings the full concentration bounds with it.

Every pair, in every small graph #

For forests, connected subgraphs and matchings, no such argument is known. The forests and connected subgraphs are conjectured to behave like trees; matchings are not. The census checks all four.

For every labelled graph on three to six vertices — 33,864 graphs — the computation enumerates every subset of edges. That is $3^{15}$, about fourteen million subsets, for the six-vertex graphs alone. It keeps those in the family and, for every pair of edges, compares $N N_{ef}$ with $N_e N_f$ exactly. The result is unambiguous. No pair of edges in any of these graphs is positively correlated in a random spanning tree, a random forest or a random connected subgraph. That is 787,830 tree pairs and 860,160 forest pairs on six vertices alone, and 871,926 forest pairs across all sizes. The matchings are different: 45 of the 240 pairs on four vertices are positively correlated, and 307,260 of the 860,160 on six.

The largest ratios are reported for graphs with no cut vertex, and the restriction matters. If a graph falls into two pieces joined at a single vertex, every tree or forest of it is a tree or forest of each piece chosen independently. Edges in different pieces are then exactly independent, and the ratio is exactly one for a reason that says nothing about the conjecture. On graphs without a cut vertex the trees still reach one, at the balanced bridge, while the forests reach $0.7778$, $0.9694$, $0.9951$ and $0.9994$ as the number of vertices goes from three to six. Never one.

Trees repel harder than forests #

The ratios can be gathered into a distribution, and the two families look different.

The tree ratios spread down to $0.5$ and below, while the forest ratios bunch close to one. A spanning tree has exactly $n - 1$ edges, so every edge that is present takes up one of a fixed number of places, and one edge’s presence crowds the others hard. A forest has no fixed size. An extra edge can simply be added if it closes no cycle, so the crowding is weaker and comes only from cycles. That is the intuition behind the conjecture, and also why it is hard. The repulsion is weak enough that a proof must be sharp, with no slack to spare.

The closest calls #

The pairs that come nearest to independence show where a counterexample would have to be.

The tightest pairs sit in graphs where the two edges are far apart in a well-connected graph, joined by many routes but with no short cycle containing both. Their interaction comes only through long cycles, which a random forest rarely completes, so it is weak. As the graphs grow the closest calls creep towards one, and a counterexample, if one exists, would sit in a large graph where the two edges’ interaction is dominated by some subtle cancellation.

Geoffrey Grimmett and Stephan Winkler ran the same check in 2004 on every graph with up to eight vertices and found no counterexample. The census here repeats their search to six vertices and agrees with it. Neither search says anything about larger graphs.

Matchings attract #

The matchings are the contrast that keeps the conjecture from being obvious, because they show that “random subsets with a constraint” do not repel in general.

In a matching, two edges that share a vertex cannot both be present, so they repel absolutely. But each edge also excludes its neighbours, and an edge two steps away benefits from that exclusion. On the path of four edges, edge 1 lies in 3 of the 8 matchings, edge 3 in 2, and both in 1, so the ratio is $4/3$: the first edge’s presence makes the third more likely. Matchings repel neighbours and attract the edges beyond them, alternating with distance, and the census’s 307,260 positive pairs on six vertices are this effect, over and over.

Forests have a superficially similar structure — an edge can exclude another by closing a cycle with it — but the exclusions are never this direct. A forest’s constraint involves whole cycles rather than single neighbours, and the conjecture says that this softer constraint never turns into attraction.

How a random walk draws a uniform tree #

Sampling a uniform spanning tree of a large graph sounds as hard as counting them, but random walks do it directly. The first method, found independently by David Aldous and Andrei Broder around 1989, runs a single random walk until it has visited every vertex and keeps, for each vertex other than the start, the edge by which the walk first entered it. Those edges always form a spanning tree, and remarkably the tree is exactly uniform. The reason is the walk’s reversibility, the same property that makes a chain that runs the same backwards look identical in either direction of time.

Wilson’s algorithm, used in the last figure, is faster. It runs walks from each vertex in turn and erases their loops. The link to electricity runs through the same walks. The chance that a random walk crosses an edge on its way between two points is a current, and currents and resistances are the language in which Kirchhoff’s probabilities are written. The spanning tree, the random walk and the electrical network are three descriptions of one object. Its edge probabilities are resistances, it is sampled by walks, and it is counted by the determinant of the sixteen trees on four points, generalised to every graph.

None of the three descriptions extends to forests. A random walk has no natural way to stop growing and leave a vertex uncovered, and a network has no natural resistance that counts acyclic sets of every size. That absence is the conjecture’s difficulty seen from another side.

What repulsion buys: concentration #

The reason negative correlation matters for concentration is the one drawn without putting back gave. A sum of negatively associated indicators concentrates at least as well as a sum of independent ones with the same probabilities, so every Chernoff and Hoeffding bound applies to it unchanged. For spanning trees the effect can be large.

The trees are drawn by David Wilson’s algorithm of 1996. A random walk is run from each vertex not yet in the tree until it hits the tree, its loops are erased, and the remaining path is added. The result is exactly uniform. Each tree has 143 edges, and the number lying wholly in the left half of the grid averages 68.3. Independent edges with the same individual chances would vary with a variance of about 31. The trees vary with a variance of 1.9.

The constraint that a tree has exactly $n - 1$ edges, and contains no cycles, ties the left half’s count to how many separate pieces the tree breaks into there. That number barely moves. Negative correlation guarantees that the variance is no larger than the independent one. Here it is sixteen times smaller, because the dependence is not only negative but strong.

Robin Pemantle and Yuval Peres proved in 2014 that every Lipschitz function of a uniform spanning tree’s edges concentrates as well as it would for independent edges — the bounded-differences principle of no single input can move it far, extended to a dependent input. Their tool was the strong Rayleigh property, a stronger relative of negative association with roots in the same electrical theory. The theorem is the forest conjecture’s payoff for trees, and a proof of the conjecture for forests would bring the same concentration with it.

What the census cannot settle #

The census settles the question for every labelled graph up to six vertices, which is a statement about a finite set and nothing more. The ratios creeping towards one could reach it in some larger graph, and nothing in the figures rules that out. Grimmett and Winkler’s eight-vertex search extends the evidence. It is still evidence about graphs small enough that every edge interacts with every other through short cycles, the regime least likely to hide a counterexample.

The census also checks only pairs. Negative correlation for pairs is the weakest of a hierarchy of properties — negative association, the strong Rayleigh property — and even a proof for pairs would leave the stronger statements open. Those are what the concentration bounds actually need. For trees all of them hold. For forests none is proved.

Still open: forests and connected subgraphs #

The uniform spanning forest conjecture asks for negative correlation of edges in a uniformly random forest of any finite graph. It is a special case, at a particular limit, of conjectures about the random-cluster model of statistical physics, where edges are kept with a probability weighted by the number of components, with weight $q < 1$. The connected-subgraph conjecture is another limit of the same model. Both are supported by every computation and both are open. Partial results establish them for special classes of graphs, by arguments that use the class’s structure and do not extend.

What would settle them is unclear. The tree proof uses electricity, and there is no network whose resistances count forests. The strong Rayleigh theory that handles trees has been extended to some generalisations of spanning trees, and forests are not among them. A counterexample is not ruled out either, and a search in larger graphs guided by the structure of the closest calls is a plausible way one might be found. That the closest calls approach one so steadily is the strongest hint that if the conjecture is true, it is true with no room to spare.

Electricity for one family, faith for the next #

Uniform random spanning trees repel their edges because contracting a resistor can only lower the resistance across another, which is Rayleigh’s principle. The balanced bridge is the one place where the repulsion vanishes. Forests and connected subgraphs, the trees’ nearest relatives, repel on every one of the hundreds of thousands of pairs that can be checked, ever more faintly as graphs grow, with no reason anyone can prove. Matchings, which look similar, attract edges two steps apart and fail at once. The difference between a theorem, a conjecture and a falsehood sits in how the constraint on a random edge set is shaped.