From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees
Abstract
We uncover a close connection between the second moment of the degree of a typical vertex in a random subgraph and the pairwise negative correlation (p-NC) property. On one hand, we exploit this connection to prove the p-NC property for non-adjacent edges in minimal spanning trees on complete graphs. On the other hand, we apply the classical p-NC property of uniform spanning trees to derive a universal upper bound on the second moment of the degree of a uniformly chosen vertex in uniform spanning trees on finite, connected, regular graphs, thereby resolving an open question posed by Nachmias and Peres. Furthermore, we determine that the optimal upper bound is exactly 6, and the method for achieving this optimal bound is interesting in itself -- the proof uses Edmonds' matroid polytope theorem.
Related
- Negative moments of the support function and applications to isotropic convex bodies
- Regime-Aware Estimation of Large Equity Correlation Matrices: Tail-Pairwise Dependence and Dynamic Conditional Correlation Decomposition for Water and Energy Sectors
- Twisted second moments of Dirichlet L-functions with applications to weighted one-level density
- Sequences of generalized moments and their applications to some moment partial differential equations
- Negative edge correlation in complete bipartite graphs
BibTeX
@misc{tang2026from,
title = {{From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees}},
author = {Pengfei Tang and Zibo Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.01444},
eprint = {2605.01444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.01444},
}
RIS
TY - UNPB
TI - From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees
AU - Pengfei Tang
AU - Zibo Zhang
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2605.01444
UR - https://arxiv.org/abs/2605.01444
AB - We uncover a close connection between the second moment of the degree of a typical vertex in a random subgraph and the pairwise negative correlation (p-NC) property. On one hand, we exploit this connection to prove the p-NC property for non-adjacent edges in minimal spanning trees on complete graphs. On the other hand, we apply the classical p-NC property of uniform spanning trees to derive a universal upper bound on the second moment of the degree of a uniformly chosen vertex in uniform spanning trees on finite, connected, regular graphs, thereby resolving an open question posed by Nachmias and Peres. Furthermore, we determine that the optimal upper bound is exactly 6, and the method for achieving this optimal bound is interesting in itself -- the proof uses Edmonds' matroid polytope theorem.
ER -