Pith. sign in

REVIEW 4 minor 1 cited by

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

T0 review · 0 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any two edges of a random minimum spanning tree, the probability that both are in the tree is at most 8 times the product of their individual probabilities, and on the complete graph the naive negative-correlation inequality holds…

desk verdict A clean, self-contained paper that settles the main open questions on MST pair correlations; the proofs are solid and the results are worth serious refereeing. read the letter →

arxiv 2608.06816 v1 pith:UK74JNNG submitted 2026-08-07 math.PR math.CO

Anish Gupta This is my paper · ORCID
classification math.PRmath.CO MSC 60C0505C8005C85
keywords minimumspanningtreenegativecorrelationpairmultiplicativecoalescentuniversalboundcompletegraphbottleneckdistancerandomedgeweights
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Random minimum spanning trees are not negatively correlated in general, but this paper proves that positive correlation is uniformly bounded: for any two distinct edges $e$ and $f$, the probability that both lie in the tree is at most 8 times the product of their individual probabilities, provided all edges receive independent weights from one common distribution with no atoms. On the complete graph $K_n$, the opposite conclusion holds: for every $n \geq 3$ the naive inequality $\mathbf{P}(e,f \in T) \leq \mathbf{P}(e \in T)\mathbf{P}(f \in T)$ is true, strictly, for adjacent pairs and for disjoint pairs when $n \geq 4$, so the tree measure has full pairwise negative correlation at every size. The engine of the complete-graph result is an exact identity $\mathbf{E}[\deg(x)^2] = 10(n-1)/n - 4\mathbf{E}[L_n]$ connecting the second moment of a vertex degree to the expected total weight $L_n$ of the minimum spanning tree; its asymptotic limit $10 - 4\zeta(3)$ answers an open question. The paper also shows the common-law assumption is essential: once edges are allowed different laws, already on $K_4$ the correlation ratio tends to infinity, so no fixed constant can work.

What carries the argument

For the universal bound, freeze all weights except the two marked edges $e,f$; conditionally on this environment, the indicators $\mathbf{1}_{\{e\in T\}}$ and $\mathbf{1}_{\{f\in T\}}$ are monotone in opposite directions, so a correlation inequality for monotone functions on product spaces gives conditional negative correlation pointwise. The remaining environmental covariance is controlled by the bottleneck distances $A$ and $B$ between the endpoints of $e$ and $f$ in the graph with both edges deleted (the smallest weight threshold at which the endpoints become connected): the conditional inclusion probability sits between $A/2$ and $A$, and the tail of such a distance is submultiplicative, $\mathbf{P}(A>s+t)\le \mathbf{P}(A>s)\mathbf{P}(A>t)$, which yields $\mathbf{E}[A^2]\le 2(\mathbf{E}A)^2$. For the complete graph, the mechanism is the accepted-merger coalescent: giving every edge an independent rate-one exponential clock and accepting edges greedily produces the multiplicative coalescent, in which two blocks of sizes $a,b$ merge with probability proportional to $ab$. The identity $\mathbf{E}[\deg(x)^2] = 10(n-1)/n - 4\mathbf{E}[L_n]$ emerges from the functional $H=\sum(1/a+1/b)$ over the $n-1$ mergers, via the pathwise relation $H=(n-1)/n+J$; a chronological lower bound $J\ge H_{n-1}$ gives the adjacent-pair theorem, and a one-step convexity bound $\mathbf{E}[J]\le (n-1)(n+2)/(4n)$ gives the disjoint-pair theorem.

What would settle it

Run an exact dynamic program over edge orders, or sample exhaustively, on finite connected multigraphs with independent uniform edge weights and look for a pair of distinct edges with $\mathbf{P}(e,f\in T)>8\,\mathbf{P}(e\in T)\mathbf{P}(f\in T)$; the paper's own exhaustive census over all small graphs finds ratios no larger than about $1.0048$, so any ratio above $8$ would refute Theorem A. Alternatively, compute $p_1$ on $K_n$ for large $n$: any $n\geq 3$ with $p_1\geq 4/n^2$, or any $n\geq 4$ with $p_2\geq 4/n^2$, would refute Theorems B1 and B2.

Watch

Extended reading notes

Core claim

The paper establishes three intertwined results. Theorem A states that for every finite connected multigraph with independent and identically distributed atomless edge weights and distinct edges $e,f$, $\mathbf{P}(e,f\in T)\leq 8\,\mathbf{P}(e\in T)\mathbf{P}(f\in T)$, and the constant arises from a clean decomposition: conditional negative correlation for the two edge indicators given all other weights, plus a second-moment bound on the bottleneck distances between their endpoints. Theorems B1 and B2 state that on $K_n$, with $p_1$ and $p_2$ the joint inclusion probabilities of two fixed adjacent and two fixed disjoint edges, $p_1<4/n^2$ for all $n\geq 3$ and $p_2<4/n^2$ for all $n\geq 4$, settling the adjacent case left open and giving strict pairwise negative correlation at every size. Proposition D1, the key finite identity $\mathbf{E}[\deg(x)^2] = 10(n-1)/n - 4\mathbf{E}[L_n]$, reduces both inequalities to bounds on the expected MST weight; combining it with known expansions yields $\lim_n \mathbf{E}[\deg(x)^2] = 10 - 4\zeta(3) = 5.1917723873616\ldots$ and the limits $2-\zeta(3)$ and $1$ for the adjacent and disjoint correlation ratios. Theorem C closes the picture by showing that if the independence assumption is kept but identical laws are dropped, no universal constant exists: on $K_4$ with two edges of law $x^t$ and four uniform edges, the ratio grows like $4t/45$.

Load-bearing premise

Everything rests on the single premise that all edge weights come from one common distribution with no atoms; the paper shows that if independent weights are allowed to have different laws, a $K_4$ example already drives the correlation ratio to infinity, so no constant of the theorem can survive.

Editorial extensions

If this is right

  • The true optimal constant in the universal bound lies between $13938405/13872419$ (a three-hub simple graph) and $8$, with the factor improving to $2+o(1)$ when both edge probabilities tend to zero.
  • For every $n\geq 3$, the minimum spanning tree measure on $K_n$ is pairwise negatively correlated, so the positive-correlation phenomenon seen on small non-complete graphs never appears in the complete graph.
  • The identity $\mathbf{E}[\deg(x)^2] = 10(n-1)/n - 4\mathbf{E}[L_n]$ converts any estimate of the expected MST weight into an estimate of the degree second moment; asymptotically it yields $10-4\zeta(3)$ for the second moment and the limiting pair ratios $2-\zeta(3)$ and $1$.
  • The expected MST weight on $K_n$ satisfies explicit all-$n$ bounds $\mathbf{E}[L_n]\geq 1 + H_{n-1}/n - 1/n^2$ and $\mathbf{E}[L_n]\leq (n-1)(5n+6)/(4n^2)$, supplying an effective finite-range estimate of a quantity previously treated mostly asymptotically.
  • No universal constant exists for independent but non-identically distributed weights, so the common-law hypothesis is not a technical convenience but a necessary condition for the bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The factor-8 proof is modular: pointwise conditional negative correlation plus a second-moment bound on bottleneck distances. The same module should apply to other greedy, order-driven random structures (random greedy matchings, random priority trees), where the bottleneck distance becomes a percolation first-passage time with submultiplicative tail.
  • Because Proposition D1 rewrites the conjectured large-$n$ decrease of $\mathbf{E}[L_n]$ as a lower bound on differences of degree second moments, a direct coupling between the coalescent at sizes $n$ and $n+1$ might prove that monotonicity without asymptotic expansions.
  • The non-identical counterexample uses a max-of-$t$ law on two edges, suggesting that what destroys the universal bound is the loss of exchangeability rather than the shape of the marginal law; an automorphism-invariant family with distinct laws assigned over orbits might still admit a finite constant.
  • Exhaustive search over small simple graphs and the hub construction together suggest that the true supremum for simple graphs is close to $1.0048$ rather than near $8$; a focus on hub-like or split graphs may be the fastest route to the optimal constant.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies pairwise correlations of edge-inclusion indicators in the minimum spanning tree of a finite connected multigraph with independent identically distributed atomless edge weights. It proves Theorem A, a universal bound p_ef ≤ 8 p_e p_f; on K_n, Theorems B1 and B2 establish strict pairwise negative correlation for adjacent and disjoint pairs for every n≥3 and n≥4, respectively. The key exact identity is Proposition D1, E[deg(x)^2] = 10(n−1)/n − 4E[L_n], which reduces the complete-graph pair probabilities to the expected MST weight and yields the PWIT second-moment limit. The paper also gives explicit positive-correlation examples, including a simple graph, computes the maximum in a parallel-bundle family, and proves Theorem C that no universal constant survives when the edge laws are independent but not identical. The proofs are analytic; finite exact computations are documented in an appendix with a companion repository.

Significance. The universal factor 8 answers an open question of R. Lyons recorded by Tang and Zhang and appears to be the first uniform multiplicative bound for MST edge correlations. The complete-graph negative correlation at every size closes the adjacent-pair case left open in [19] and gives an effective proof of the disjoint-pair property without local weak convergence or Fatou's lemma. Proposition D1 is a clean finite identity with independent interest, and Corollary D3 identifies the degree second-moment limit with 10−4ζ(3). The paper is unusually careful: the central theorems are derived without fitted parameters, the finite theorems are cleanly separated from the asymptotic external inputs, and the computational appendix provides exact rational cross-checks, including several documented failed strengthenings. The main limitation, that Theorem A requires one common atomless law, is explicitly delimited by Theorem C rather than hidden.

minor comments (4)
  1. [§5.3, Lemma 5.5, Corollary D2] The harmonic-number expressions are ambiguous as submitted: Lemma 5.5 should state J≥H_n−1, and the strengthened lower bound in Corollary D2 should be 1+(H_n−1)/n−1/n^2. If H_{n−1} is read instead, the claimed equality at n=2 fails, so the typesetting should make the distinction explicit.
  2. [§1.5, §5.3, Lemma 5.3] The displayed identity H=n−1/n+J should be typeset as H=n−1/n+J (that is, n minus 1/n) and similarly in the proof of Theorem B1. In plain text the current notation can easily be misread as (n−1)/n, which would make the identity false; the surrounding algebra shows the intended meaning, but the ambiguity should be removed.
  3. [Appendix A] Since Propositions 4.2–4.4 and Table 1 rely on exact rational computations, the companion repository and the archived DOI should be checked for permanence and versioning, and the manuscript should state which repository files reproduce each table row and certificate.
  4. [§4.4, Theorem C] The asymptotic expansion R(t)=4t/45+46/75+O(t^{−1}) is mathematically correct, but a reader may expect O(1) after a growing main term; one sentence clarifying that the expansion is to constant order would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core theorems are derived from first principles and standard external inequalities, with no fitted parameters or load-bearing self-citations.

full rationale

The paper's central derivation chain is self-contained. Theorem A is built from the Kruskal/cycle characterization (Lemma 2.1), conditional negative correlation via Harris's inequality (Lemma 3.3), a pointwise deletion sandwich comparing conditional inclusion probabilities with bottleneck distances (Lemma 3.4), and a sprinkling-based second-moment bound (Lemma 3.1); each ingredient is proved in the paper from first principles, with Harris's inequality as the only external input, itself a classical theorem. The complete-graph results rest on the accepted-merger coalescent (Lemma 5.1), which is derived from exponential memorylessness, together with pathwise accounting (Lemma 5.3), the degree-functional update (Lemma 5.4), the chronological reciprocal bound (Lemma 5.5), and the one-step partition inequality (Lemma 5.6); no asymptotic or fitted value is used in Theorems B1 and B2. Proposition D1 is an exact identity expressing E[deg(x)^2] as 10(n-1)/n - 4E[L_n], and Corollary D2 merely rearranges this identity by counting adjacent and disjoint edge pairs; the external expansions of Cooper et al. [6] and Li and Zhang [13] are used only in Corollary D3 and Corollary 6.3 to convert the finite identity into limit and rate statements, not to prove any finite theorem. There are no fitted parameters renamed as predictions, no author self-citations of any kind, and no uniqueness theorem imported from prior work by the same author. The limitation noted in Remark 6.2, that Theorem B2 may be a new complete-range proof of a known bound, concerns possible novelty overlap rather than circularity, since the bound is proved from the coalescent rather than assumed. Theorem C is computed directly from the four-terminal formula of Lemma 4.1, and the Appendix explicitly separates finite computer checks from analytic proofs without using them as evidence for the universal theorems.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central finite theorems use no fitted parameters and introduce no new objects. The only unproved inputs are standard facts and cited asymptotic results, which are external and used only for limiting statements.

assumptions (6)
  • standard math Kruskal cycle characterization: an edge belongs to the MST iff its endpoints are disconnected in the subgraph of strictly lighter edges.
    Proved as Lemma 2.1 and used in every conditional acceptance argument.
  • standard math Harris's inequality for monotone functions on product spaces.
    Used in Lemma 3.3 to get conditional negative correlation after the coordinate change (U,1-V).
  • domain assumption For an atomless common law, the MST law depends only on the order of weights, and applying the CDF maps weights to i.i.d. Uniform[0,1].
    Assumed throughout Section 3 and used to reduce to uniform and exponential weights.
  • standard math Exponential memorylessness yields the multiplicative coalescent merger probabilities in Lemma 5.1.
    Used in Section 5 for the accepted-merger process on K_n.
  • domain assumption Known asymptotic expansions of E[L_n] (Cooper et al. [6], Li and Zhang [13]) are correct.
    Invoked only in Corollary D3 and Corollary 6.3 for limits and rates; not needed for Theorems A, B1, or B2.
  • domain assumption The root degree second moment in the wired minimal spanning forest on the Poisson-weighted infinite tree equals 10-4ζ(3), as stated in [19, Proposition 3.11].
    Used only to identify the limit in Corollary D3 and answer Question 3.8.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pairwise edge correlations in random minimum spanning trees: a universal bound and complete-graph negative correlation." pith.science (2026). https://pith.science/paper/UK74JNNG

@misc{pith2026260806816,
  author       = {Pith},
  title        = {Pith review of: Pairwise edge correlations in random minimum spanning trees: a universal bound and complete-graph negative correlation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UK74JNNG}},
  note         = {Machine review of arXiv:2608.06816}
}
abstract

Let $G$ be a finite connected multigraph whose edges receive independent weights from one atomless law, and let $\operatorname{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)\leq 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\geq 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.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Fixed forests in the minimum spanning tree and cubic volume growth

    math.PR 2026-08 accept novelty 8.0 of 10

    For the complete-graph minimum spanning tree with random edge weights, fixed-forest inclusion probabilities factorize over components, and the expected radius-r ball size is asymptotically r^3/36.

Reference graph

Works this paper leans on

20 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [19]

    Tang and Z

    P. Tang and Z. Zhang.From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees. Preprint, arXiv:2605.01444v1, 2026

    arXiv 2026

  2. [1]

    Addario-Berry.The local weak limit of the minimum spanning tree of the complete graph

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

    arXiv 2013

  3. [2]

    Aldous.Brownian excursions, critical random graphs and the multiplicative coalescent

    D. Aldous.Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25(1997), 812–854

    work page 1997

  4. [3]

    R. E. Barlow and F. Proschan.Statistical Theory of Reliability and Life Testing: Probability Models. Holt, Rinehart and Winston, New York, 1975

    work page 1975

  5. [4]

    Beveridge, A

    A. Beveridge, A. M. Frieze and C. J. H. McDiarmid.Random minimum length spanning trees in regular graphs. Combinatorica18(1998), 311–333

    work page 1998

  6. [5]

    Brändén and J

    P. Brändén and J. Huh.Lorentzian polynomials. Ann. of Math. (2)192(2020), 821–891

    work page 2020

  7. [6]

    Cooper, A

    C. Cooper, A. Frieze, N. Ince, S. Janson and J. Spencer.On the length of a random minimum spanning tree. Combin. Probab. Comput.25(2016), 89–107

    work page 2016

  8. [7]

    Local limit of Prim's algorithm

    B. Corsini, R. Gündlach and R. van der Hofstad.Local limit of Prim’s algorithm. Preprint, arXiv:2507.04867, 2025

    work page Pith review arXiv 2025

Show all 20 references
  1. [8]

    J. A. Fill and J. M. Steele.Exact expectations of minimal spanning trees for graphs with random edge weights. In: Stein’s Method and Applications, Singapore Univ. Press, 2005, 169–180

    2005

  2. [9]

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

    1985

  3. [10]

    Gamarnik.The expected value of random minimal length spanning tree of a complete graph

    D. Gamarnik.The expected value of random minimal length spanning tree of a complete graph. In: Proceedings of the Sixteenth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2005), ACM, New York, 2005, 700–704

    2005

  4. [11]

    T. E. Harris.A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc.56(1960), 13–20

    1960

  5. [12]

    Janson.The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

    S. Janson.The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph. Random Structures Algorithms7(1995), 337–355

    1995

  6. [13]

    W. V. Li and X. Zhang.On the difference of expected lengths of minimum spanning trees. Combin. Probab. Comput.18(2009), 423–434

    2009

  7. [14]

    Lyons and Y

    R. Lyons and Y. Peres.Probability on Trees and Networks. Cambridge Series in Statistical and Proba- bilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016

    2016

  8. [15]

    Lyons, Y

    R. Lyons, Y. Peres and O. Schramm.Minimal spanning forests. Ann. Probab.34(2006), 1665–1692

    2006

  9. [16]

    Nachmias and P

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

    2024

  10. [17]

    Nishikawa, P

    J. Nishikawa, P. T. Otto and C. Starr.Polynomial representation for the expected length of minimal spanning trees. Pi Mu Epsilon J.13(6) (2012), 357–365

    2012

  11. [18]

    J. M. Steele.On Frieze’sζ(3)limit for lengths of minimal spanning trees. Discrete Appl. Math.18 (1987), 99–103

    1987

  12. [20]

    Tang and Z

    P. Tang and Z. Zhang.Pairwise negative correlation for uniform spanning subgraphs of the complete graph. Preprint, arXiv:2603.10738, 2026. PAIR WISE EDGE CORRELATIONS IN RANDOM MINIMUM SPANNING TREES 21 Independent researcher Email address:ag2269@cantab.ac.uk URL:https://orcid...

    2026

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.