Pairwise edge correlations in random minimum spanning trees: a universal bound and complete-graph negative correlation

Abstract

Let G be a finite connected multigraph whose edges receive independent weights from one atomless law, and let MST(G) be the resulting random minimum spanning tree. Its law is not pairwise negatively correlated: Lyons, Peres and Schramm exhibited two positively correlated edges, and we give such an example on a simple graph. We prove that positive correlation is nevertheless uniformly controlled: P(e,f in T) <= 8 P(e in T) P(f in T), answering a question of R. Lyons recorded by Tang and Zhang. After conditioning on all other weights, Harris's inequality gives conditional negative correlation; two bottleneck distances and a sharp second-moment estimate control the remaining environmental covariance. For the complete graph K_n we prove pairwise negative correlation for every n >= 3. The key finite identity is E[deg(x)^2] = 10(n-1)/n - 4 E[L_n], where L_n is the total weight of the minimum spanning tree under rate-one exponential weights. Known expansions for E[L_n] then give the rate of convergence to 10 - 4 zeta(3) and the limits of both pair-correlation ratios. Finally, an explicit K_4 family shows that no universal constant survives when the independent edge laws need not be identical. This version supersedes v1 of 3 August 2026, which was deposited to establish a citable public version while arXiv endorsement was pending. The manuscript was substantially revised on 7 August 2026 and the exact complete-graph table was regenerated. The paper is now on arXiv as arXiv:2608.06816, which is the version of record and should be cited in preference to this deposit; this record is retained as an archival snapshot. It has not been peer reviewed. The paper and optional companion materials are maintained at https://github.com/agupta/random-mst-correlations.