pith. sign in

arxiv: 2605.01444 · v1 · submitted 2026-05-02 · 🧮 math.PR

From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees

Pengfei Tang , Zibo Zhang This is my paper

Pith reviewed 2026-05-09 18:28 UTC · model grok-4.3

classification 🧮 math.PR
keywords minimal spanning treesuniform spanning treespairwise negative correlationsecond momentsvertex degreesregular graphsmatroid polytope
0
0 comments X

The pith

The second moment of vertex degrees in random subgraphs controls their pairwise negative correlation property, yielding new results for minimal and uniform spanning trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a connection between the second moment of the degree of a typical vertex in a random subgraph and the pairwise negative correlation property of its edges. It uses this connection to prove that non-adjacent edges in minimal spanning trees on complete graphs are pairwise negatively correlated. It also applies the known pairwise negative correlation property of uniform spanning trees to prove that the second moment of the degree of a uniformly chosen vertex is at most 6 in uniform spanning trees on finite connected regular graphs, resolving an open question. The bound of 6 is shown to be optimal through a proof that invokes Edmonds' matroid polytope theorem.

Core claim

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. We exploit this connection to prove the p-NC property for non-adjacent edges in minimal spanning trees on complete graphs. 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. Furthermore, we determine that the optimal upper bound is exactly 6, with the proof using Edmonds' matroid polytope theorem.

What carries the argument

The link from the second moment of a typical vertex's degree in a random subgraph to the pairwise negative correlation property of its edges, combined with Edmonds' matroid polytope theorem to achieve the sharp bound of 6.

If this is right

  • Non-adjacent edges in minimal spanning trees on complete graphs are pairwise negatively correlated.
  • The second moment of the degree of a uniformly chosen vertex is at most 6 in uniform spanning trees on any finite connected regular graph.
  • The upper bound of 6 on this second moment is optimal.
  • The optimality proof relies on Edmonds' matroid polytope theorem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The connection between second moments and pairwise negative correlation might apply to other random subgraphs or random structures from matroids.
  • Controlling degree second moments could help derive concentration results for other properties of spanning trees, such as the number of leaves.
  • The pairwise negative correlation result for minimal spanning trees might extend to graphs that are not complete.
  • Similar techniques could analyze variance or moments in random spanning structures on non-regular graphs.

Load-bearing premise

The connection between second moments of vertex degrees and pairwise negative correlation holds for minimal spanning trees on complete graphs and uniform spanning trees on regular graphs.

What would settle it

An explicit calculation for some finite connected regular graph showing that the second moment of vertex degree in its uniform spanning tree exceeds 6 would disprove the universal bound.

Figures

Figures reproduced from arXiv: 2605.01444 by Pengfei Tang, Zibo Zhang.

Figure 1
Figure 1. Figure 1: The sharpness construction for the constant 6. The left panel shows the one-port dense block Bd: start with Kq, delete the two edges {o, a}, {o, b}, and delete a perfect matching on the remaining q − 3 = d − 1 vertices. The right panel shows Gd, obtained by attaching d disjoint copies of Bd to a new central vertex c through their ports. Lemma 4.18. For the blocks Bd constructed above, Bd is connected for a… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper establishes a link between the second moment E[deg(U)^2] of the degree of a uniform random vertex U in a random spanning tree and the pairwise negative correlation (p-NC) property of its edge indicators. One direction uses the link to prove p-NC for non-adjacent edges in minimal spanning trees on K_n. The converse invokes the classical p-NC property of uniform spanning trees on regular graphs to bound the second-moment quantity, resolving an open question of Nachmias and Peres; the optimal constant is shown to be exactly 6 by maximizing a quadratic form over the spanning-tree polytope via Edmonds' theorem.

Significance. If the derivations hold, the work supplies a new equivalence-style connection between moments and negative correlation in random spanning trees, yields a proof of p-NC for MSTs on complete graphs, and resolves the Nachmias-Peres question with a tight, parameter-free bound of 6 obtained from the matroid polytope. The explicit use of Edmonds' theorem to certify optimality is a methodological strength.

major comments (2)
  1. [§3] §3 (MST direction): the claimed equivalence between E[deg(U)^2] and the sum of Cov(1_e,1_f) over non-adjacent pairs must be verified to hold without additional assumptions on the edge-weight distribution; the reduction appears to rely on the specific structure of the MST on K_n.
  2. [§4.2] §4.2 (UST bound): the maximization of (1/n)∑_v (x_v + x_v^2) subject to the spanning-tree polytope constraints and ∑x_v=2(n-1) is asserted to yield supremum 6; the argument that cut constraints force Var(x_v)=O(1/n) and that the bound is asymptotically sharp should be checked against the explicit facet description in Edmonds' theorem.
minor comments (3)
  1. [Introduction] Define the random variable U (uniform vertex) and the precise statement of p-NC at the first use in the introduction for readability.
  2. [Theorem 1.2] In the statement of the optimal bound (Theorem 1.2 or equivalent), clarify whether the constant 6 is achieved for finite n or only in the large-n limit.
  3. [§4] Add a short remark comparing the obtained bound of 6 with known degree-concentration results for USTs on regular graphs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and positive recommendation for minor revision. We address each major comment below and will incorporate clarifications where appropriate.

read point-by-point responses

  1. Referee: [§3] §3 (MST direction): the claimed equivalence between E[deg(U)^2] and the sum of Cov(1_e,1_f) over non-adjacent pairs must be verified to hold without additional assumptions on the edge-weight distribution; the reduction appears to rely on the specific structure of the MST on K_n.

    Authors: We appreciate the referee's attention to this detail. The equivalence in §3 is derived under the standard assumption that edge weights are i.i.d. continuous random variables, which ensures that the MST is unique almost surely. This allows us to express the degree second moment directly in terms of the edge indicators without ties. The reduction is specific to the complete graph K_n as the paper focuses on MSTs there, but the underlying algebraic identity between the second moment and the sum of covariances holds more generally for any graph with a unique spanning tree. We will add a clarifying sentence in the revised manuscript to explicitly state the assumption on the weight distribution. revision: yes

  2. Referee: [§4.2] §4.2 (UST bound): the maximization of (1/n)∑_v (x_v + x_v^2) subject to the spanning-tree polytope constraints and ∑x_v=2(n-1) is asserted to yield supremum 6; the argument that cut constraints force Var(x_v)=O(1/n) and that the bound is asymptotically sharp should be checked against the explicit facet description in Edmonds' theorem.

    Authors: We thank the referee for suggesting a closer examination of this part. In §4.2, the maximization of the quadratic form over the spanning-tree polytope is indeed certified using Edmonds' theorem, which characterizes the polytope via the cut constraints and the degree sum. The argument proceeds by noting that for any point in the polytope, the cut constraints imply that the variance of the x_v's is controlled, leading to the bound of 6. The asymptotic sharpness is demonstrated by considering sequences of regular graphs where the second moment approaches 6. To make this more explicit, we will expand the discussion in the revision to include a brief reference to how the facet inequalities are used in bounding the quadratic term, confirming that no additional facets are needed beyond those in Edmonds' description for this particular objective. revision: partial

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper introduces a novel connection between the second moment of a typical vertex degree and the pairwise negative correlation property for random subgraphs. This link is applied forward to establish p-NC for non-adjacent edges in MSTs on complete graphs. The converse direction invokes the externally classical p-NC property of USTs (not derived here) together with Edmonds' matroid polytope theorem to bound the second-moment quantity and optimize the constant 6 over the spanning-tree polytope. All load-bearing steps rely on independent standard theorems or the new link itself; no self-citations are load-bearing, no fitted inputs are renamed as predictions, and no definitions or ansatzes reduce by construction to the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the classical pairwise negative correlation property of uniform spanning trees (treated as given) and on Edmonds' matroid polytope theorem (standard result in combinatorial optimization). No free parameters or new invented entities are introduced in the abstract.

axioms (2)
  • standard math Pairwise negative correlation holds for uniform spanning trees (classical result)
    Invoked to derive the second-moment bound for UST on regular graphs.
  • standard math Edmonds' matroid polytope theorem
    Used to prove that the upper bound of 6 is optimal.

pith-pipeline@v0.9.0 · 5428 in / 1422 out tokens · 25344 ms · 2026-05-09T18:28:28.517854+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    The local weak limit of the minimum spanning tree of the complete graph

    Louigi Addario-Berry. The local weak limit of the minimum spanning tree of the complete graph.arXiv preprint arXiv:1301.1667, 2013

    work page Pith review arXiv 2013

  2. [2]

    Louigi Addario-Berry, Simon Griffiths, and Ross J. Kang. Invasion percolation on the Poisson- weighted infinite tree.Ann. Appl. Probab., 22(3):931–970, 2012

    work page 2012

  3. [3]

    Processes on unimodular random networks.Electron

    David Aldous and Russell Lyons. Processes on unimodular random networks.Electron. J. Probab., 12:no. 54, 1454–1508, 2007

    work page 2007

  4. [4]

    Michael Steele

    David Aldous and J. Michael Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. InProbability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 1–72. Springer, Berlin, 2004. 27

    work page 2004

  5. [5]

    Recurrence of distributional limits of finite planar graphs

    Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13, 2001

    work page 2001

  6. [6]

    Lorentzian polynomials.Ann

    Petter Br¨ and´ en and June Huh. Lorentzian polynomials.Ann. of Math. (2), 192(3):821–891, 2020

    work page 2020

  7. [7]

    Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances.Ann

    Robert Burton and Robin Pemantle. Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances.Ann. Probab., 21(3):1329–1371, 1993

    work page 1993

  8. [8]

    Submodular functions, matroids, and certain polyhedra

    Jack Edmonds. Submodular functions, matroids, and certain polyhedra. InCombinatorial Structures and Their Applications, pages 69–87. Gordon and Breach, New York, 1970

    work page 1970

  9. [9]

    Ellens, F

    W. Ellens, F. M. Spieksma, P. Van Mieghem, A. Jamakovic, and R. E. Kooij. Effective graph resistance.Linear Algebra Appl., 435(10):2491–2506, 2011

    work page 2011

  10. [10]

    Airy phenomena and analytic combinatorics of connected graphs.Electron

    Philippe Flajolet, Bruno Salvy, and Gilles Schaeffer. Airy phenomena and analytic combinatorics of connected graphs.Electron. J. Combin., 11(1):Research Paper 34, 30, 2004

    work page 2004

  11. [11]

    Ronald M. Foster. The average impedance of an electrical network. InReissner Anniversary Volume, Contributions to Applied Mechanics, pages 333–340. J. W. Edwards, Ann Arbor, MI, 1949

    work page 1949

  12. [12]

    A. M. Frieze. On the value of a random minimum spanning tree problem.Discrete Appl. Math., 10(1):47–56, 1985

    work page 1985

  13. [13]

    Gutman and W

    I. Gutman and W. Xiao. Generalized inverse of the Laplacian matrix and some applications. Bull. Cl. Sci. Math. Nat. Sci. Math., (29):15–23, 2004

    work page 2004

  14. [14]

    Correlation bounds for fields and matroids

    June Huh, Benjamin Schr¨ oter, and Botong Wang. Correlation bounds for fields and matroids. J. Eur. Math. Soc. (JEMS), 24(4):1335–1351, 2022

    work page 2022

  15. [15]

    Kirchhoff

    G. Kirchhoff. Ueber die aufl¨ osung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer str¨ ome gef¨ uhrt wird.Annalen der Physik, 148(12):497–508, 1847

    work page

  16. [16]

    Cambridge University Press, New York,

    Russell Lyons and Yuval Peres.Probability on Trees and Networks, volume 42 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York,

    work page

  17. [17]

    Available athttp://rdlyons.pages.iu.edu/

    work page

  18. [18]

    Minimal spanning forests.Ann

    Russell Lyons, Yuval Peres, and Oded Schramm. Minimal spanning forests.Ann. Probab., 34(5):1665–1692, 2006

    work page 2006

  19. [19]

    The Laplacian spectrum of graphs

    Bojan Mohar. The Laplacian spectrum of graphs. InGraph theory, combinatorics, and applications, Vol. 2. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, MI, USA, May 30-June 3, 1988, pages 871–898. New York: John Wiley & Sons, Inc., 1991

    work page 1988

  20. [20]

    E. H. Moore. On the reciprocal of the general algebraic matrix.Bulletin of the American Mathematical Society, 26(9):394–395, 1920

    work page 1920

  21. [21]

    The local limit of uniform spanning trees.Probab

    Asaf Nachmias and Yuval Peres. The local limit of uniform spanning trees.Probab. Theory Related Fields, 182(3-4):1133–1161, 2022. 28

    work page 2022

  22. [22]

    The wired minimal spanning forest on the Poisson-weighted infinite tree.Ann

    Asaf Nachmias and Pengfei Tang. The wired minimal spanning forest on the Poisson-weighted infinite tree.Ann. Appl. Probab., 34(2):2415–2446, 2024

    work page 2024

  23. [23]

    A generalized inverse for matrices.Mathematical Proceedings of the Cambridge Philosophical Society, 51(3):406–413, 1955

    Roger Penrose. A generalized inverse for matrices.Mathematical Proceedings of the Cambridge Philosophical Society, 51(3):406–413, 1955

    work page 1955

  24. [24]

    Shortest connection networks and some generalizations.The Bell System Technical Journal, 36(6):1389–1401, 1957

    Robert Clay Prim. Shortest connection networks and some generalizations.The Bell System Technical Journal, 36(6):1389–1401, 1957

    work page 1957

  25. [25]

    Limit theorems for stochastic processes.Theory of Probability & Its Applications, 1(3):261–290, 1956

    Anatoly V Skorokhod. Limit theorems for stochastic processes.Theory of Probability & Its Applications, 1(3):261–290, 1956

    work page 1956

  26. [26]

    Pairwise negative correlation for uniform spanning subgraphs of the complete graph.arXiv preprint arXiv:2603.10738, 2026

    Pengfei Tang and Zibo Zhang. Pairwise negative correlation for uniform spanning subgraphs of the complete graph.arXiv preprint arXiv:2603.10738, 2026. 29

    work page arXiv 2026