Edges of the uniform random forest of Kn are pairwise negatively correlated for every n
Abstract
Let Fn be uniform on all forests of the simple complete graph Kn, with isolated vertices allowed. A conjecture of Kahn and of Winkler, studied by Grimmett and Winkler, asserts that any two distinct edges of any finite graph are negatively correlated under the uniform forest measure. Stark proved this for G=Kn once n is sufficiently large, but did not furnish an explicit threshold. We prove it for every n≥ 2, strictly whenever two distinct edges exist. The difficulty is concentrated in the disjoint-edge orbit, whose correlation ratio tends to one. We remove this cancellation before estimating anything: the desired inequality becomes an exact comparison among the first two moments of the component count and the expected sum of squared degrees. When the component count fluctuates, this comparison contains a variance term absent from the fixed-component identities of Tang and Zhang. Component marking, tail elimination, and effective Stirling bounds control the three moments for n≥ 651; exact integer recurrences cover the remaining values.
Related
- From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees
- Mesoscopic eigenvalue statistics for correlated random matrices
- Phase transition of random non-uniform hypergraphs
- Feature Space Selection and Heterogeneous Effect Estimation for Blood-Brain Barrier Permeability: A Random Forest to the Generalized Random Forest Pipeline
- Superdiffusive central limit theorem for a Brownian particle in a critically-correlated incompressible random drift
BibTeX
@misc{gupta2026edges,
title = {{Edges of the uniform random forest of $K_n$ are pairwise negatively correlated for every $n$}},
author = {Anish Gupta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26134},
eprint = {2609.26134},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26134},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Edges of the uniform random forest of K_n are pairwise negatively correlated for every n
AU - Anish Gupta
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26134
UR - https://arxiv.org/abs/2609.26134
AB - Let F_n be uniform on all forests of the simple complete graph K_n, with isolated vertices allowed. A conjecture of Kahn and of Winkler, studied by Grimmett and Winkler, asserts that any two distinct edges of any finite graph are negatively correlated under the uniform forest measure. Stark proved this for G=K_n once n is sufficiently large, but did not furnish an explicit threshold. We prove it for every n≥ 2, strictly whenever two distinct edges exist. The difficulty is concentrated in the disjoint-edge orbit, whose correlation ratio tends to one. We remove this cancellation before estimating anything: the desired inequality becomes an exact comparison among the first two moments of the component count and the expected sum of squared degrees. When the component count fluctuates, this comparison contains a variance term absent from the fixed-component identities of Tang and Zhang. Component marking, tail elimination, and effective Stirling bounds control the three moments for n≥ 651; exact integer recurrences cover the remaining values.
ER -