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 $\mathrm{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: $\mathbf{P}(e,f\in T)\le 8\mathbf{P}(e\in T)\mathbf{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 $K_n$ we prove pairwise negative correlation for every $n\ge 3$. The key finite identity is $\mathbf{E}[\mathrm{deg}(x{)}^2]=10(n-1)/n-4\mathbf{E}[L_n]$, where $L_n$ is the total weight of the minimum spanning tree under rate-one exponential weights. Known expansions for $\mathbf{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.

21 pages. Accompanying code and exact data: https://github.com/agupta/random-mst-correlations