pith. sign in

arxiv: 2410.16830 · v4 · pith:AH2RRYEMnew · submitted 2024-10-22 · 🧮 math.PR · math.CO

Random spanning trees in random environment

Luca Makowiec , Michele Salvi , Rongfeng Sun This is my paper

Pith reviewed 2026-05-23 19:11 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords random spanning treesrandom environmentdiametercomplete graphdisorderuniform spanning treeminimum spanning tree
0
0 comments X

The pith

On the complete graph, random spanning trees in random environment have diameter of order n^{1/2} for low disorder and n^{1/3} for high disorder.

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

The paper defines the random spanning tree in random environment model on the complete graph K_n, where each spanning tree is weighted by exp(-beta times the sum of i.i.d. uniform disorder values on its edges. It proves that when beta is at most order n over log n the typical diameter is order n to the 1/2, the same scaling as the uniform spanning tree. When beta reaches order n to the 4/3 times log n the typical diameter drops to order n to the 1/3, matching the minimum spanning tree. A reader cares because the result shows how a single tunable parameter moves the geometry of a random tree between two classical extremes.

Core claim

The RSTRE is the Gibbs measure on spanning trees of K_n with energy given by the sum of edge disorders. For beta less than or equal to C n over log n the diameter is typically of order n to the 1/2 with high probability; for beta greater than or equal to n to the 4/3 log n the diameter is typically of order n to the 1/3 with high probability. The paper also conjectures that for beta equal to n to the alpha with alpha between 1 and 4/3 the diameter exponent lies strictly between 1/2 and 1/3.

What carries the argument

The RSTRE Gibbs measure over spanning trees, which weights each tree by the exponential of minus beta times its total disorder cost and thereby interpolates between uniform and minimum spanning trees as beta grows.

If this is right

  • The diameter scaling is the same as the uniform spanning tree when beta is small.
  • The diameter scaling is the same as the minimum spanning tree when beta is large.
  • An intermediate disorder regime is conjectured to produce a diameter exponent that depends on the precise power of n in beta.

Where Pith is reading between the lines

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

  • The change in diameter scaling is expected to occur at some critical beta value lying between the two identified regimes.
  • The same diameter transition may appear when the underlying graph is replaced by other dense random graphs with edge disorders.
  • Numerical sampling of the model could directly test the conjectured intermediate scaling exponent for beta equal to n to the alpha with alpha in (1,4/3).

Load-bearing premise

The edge disorders are i.i.d. uniform random variables on the complete graph K_n.

What would settle it

Sampling many RSTRE realizations at beta equal to n to the 4/3 log n and checking whether the diameters concentrate around n to the 1/3 rather than around a different power of n.

Figures

Figures reproduced from arXiv: 2410.16830 by Luca Makowiec, Michele Salvi, Rongfeng Sun.

Figure 1
Figure 1. Figure 1: Typical vertices x and y are likely to be connected in T via a short path from x to TC1ppmq , a path inside TC1ppmq and another short path from TC1ppmq to y. f with ωf ď p. The series law (Lemma 2.2) and Rayleigh’s monotonicity principle (Theorem 2.3) give that the effective resistance can be upper bounded by the length of γpu, vq times the maximum resistance along γpu, vq. For such ω we have P ω n,βn pe P… view at source ↗
Figure 2
Figure 2. Figure 2: The path γT pu, vq can be decomposed into a path Γu, an edge e and another path Γv . After the contraction of Γu and Γv , the edge e becomes an edge between u and v in pG 1 , wq. Using several union bounds and (4.6) then gives Pp ˆ ď u,vPVn u‰v Fpu, vq ˙ ď ÿ u,vPVn u‰v ÿ ePEn Pp ` Fpu, v; eq ˘ ď n 5 e ´βnpq´pq , completing the proof. □ 4.3. Diameter of the supercritical component. The next step is to show … view at source ↗
read the original abstract

We introduce a new spanning tree model called the random spanning tree in random environment (RSTRE), which interpolates between the uniform spanning tree and the minimum spanning tree as the inverse temperature (disorder strength) $\beta$ varies. On the complete graph with $n$ vertices and i.i.d.\ uniform disorder variables on the edges, we identify: (1) a low disorder regime with $\beta \leq C n/\log n$, where the diameter of the random spanning tree is typically of order $n^{1/2}$, the same as for the uniform spanning tree; (2) a high disorder regime with $\beta \geq n^{4/3} \log n$, where the diameter is typically of order $n^{1/3}$, the same as for the minimum spanning tree. We conjecture that for $\beta=n^{\alpha}$ with $\alpha \in (1, 4/3)$, the diameter is of order $n^{\gamma+o(1)}$ for some $\gamma=\gamma(\alpha)$ strictly between $1/2$ and $1/3$.

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

1 major / 0 minor

Summary. The manuscript introduces the random spanning tree in random environment (RSTRE) model on the complete graph K_n, which depends on an inverse-temperature parameter β and interpolates between the uniform spanning tree (low β) and the minimum spanning tree (high β) via i.i.d. uniform edge disorders. It identifies a low-disorder regime β ≤ C n / log n in which the typical diameter is of order n^{1/2} and a high-disorder regime β ≥ n^{4/3} log n in which the typical diameter is of order n^{1/3}, while conjecturing an intermediate scaling n^γ(α) for β = n^α with α ∈ (1, 4/3).

Significance. If rigorously established, the identification of explicit thresholds separating UST-like and MST-like diameter scalings in a single parameterized family would be a notable contribution to the study of disorder effects on random combinatorial objects, potentially enabling further analysis of phase transitions in spanning-tree geometry.

major comments (1)
  1. [Abstract] Abstract: the central claims on the two diameter regimes are stated without any proof sketches, key estimates, technical lemmas, or error bounds, so the support for the asserted scalings cannot be assessed from the supplied text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their comments. We respond to the single major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claims on the two diameter regimes are stated without any proof sketches, key estimates, technical lemmas, or error bounds, so the support for the asserted scalings cannot be assessed from the supplied text.

    Authors: The abstract is a high-level summary of the main theorems. The full manuscript contains the complete proofs, including all key estimates, technical lemmas, and error bounds establishing the n^{1/2} diameter in the low-disorder regime β ≤ C n / log n and the n^{1/3} diameter in the high-disorder regime β ≥ n^{4/3} log n. The support for the claims is therefore present in the body of the paper rather than the abstract itself. If the referee means that the entire manuscript lacks these elements, we would welcome specific pointers to sections that require strengthening. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines a new interpolated model (RSTRE) on K_n with i.i.d. uniform edge weights and states asymptotic diameter regimes that recover the known UST scaling n^{1/2} for small β and MST scaling n^{1/3} for large β. No equations, fitted parameters, or self-citations appear in the provided claims; the results are presented as new model behavior rather than reductions of prior fitted quantities or self-referential definitions. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

Central claim rests on the new model definition, the i.i.d. uniform disorder assumption, and known diameter asymptotics of UST and MST. No free parameters are fitted to data; β thresholds are presented as derived quantities.

axioms (2)
  • domain assumption Edge disorders are i.i.d. uniform random variables on the complete graph K_n.
    Explicitly stated as the setting for the diameter results.
  • standard math Diameter of uniform spanning tree is order n^{1/2} and of minimum spanning tree is order n^{1/3}.
    Used as benchmark behaviors recovered in the respective regimes.
invented entities (1)
  • RSTRE model no independent evidence
    purpose: Interpolates between uniform and minimum spanning trees via β-controlled disorder weighting.
    Newly defined in the paper; no independent evidence outside this work.

pith-pipeline@v0.9.0 · 5715 in / 1342 out tokens · 31340 ms · 2026-05-23T19:11:32.635840+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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

  1. Local limits of random spanning trees in random environment

    math.PR 2024-10 unverdicted novelty 6.0

    For random spanning trees with weights exp(-β ω_e) on K_n, edge overlap transitions from ~β to ~n as β grows past n, with local limit matching uniform ST for β = o(n/log n) and min ST for β > n log^λ n.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Addario-Berry, N

    L. Addario-Berry, N. Broutin, and B. Reed. Critical random graphs and the structure of a minimum spanning tree.Random Structures Algorithms, 35(3):323–347, 2009

    work page 2009

  2. [2]

    The scaling limit of the minimum spanning tree of the complete graph.Ann

    Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt, and Grégory Miermont. The scaling limit of the minimum spanning tree of the complete graph.Ann. Probab., 45(5):3075–3144, 2017

    work page 2017

  3. [3]

    Geometry of the minimal spanning tree of a random 3-regular graph

    Louigi Addario-Berry and Sanchayan Sen. Geometry of the minimal spanning tree of a random 3-regular graph. Probab. Theory Related Fields, 180(3-4):553–620, 2021

    work page 2021

  4. [4]

    The continuum random tree

    David Aldous. The continuum random tree. I.Ann. Probab., 19(1):1–28, 1991

    work page 1991

  5. [5]

    The continuum random tree

    David Aldous. The continuum random tree. II. An overview. InStochastic analysis (Durham, 1990), volume 167 ofLondon Math. Soc. Lecture Note Ser., pages 23–70. Cambridge Univ. Press, Cambridge, 1991

    work page 1990

  6. [6]

    The continuum random tree

    David Aldous. The continuum random tree. III.Ann. Probab., 21(1):248–289, 1993

    work page 1993

  7. [7]

    David J. Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math., 3(4):450–465, 1990

    work page 1990

  8. [8]

    The diameter of the uniform spanning tree of dense graphs

    Noga Alon, Asaf Nachmias, and Matan Shalev. The diameter of the uniform spanning tree of dense graphs. Combin. Probab. Comput., 31(6):1010–1030, 2022

    work page 2022

  9. [9]

    The GHP scaling limit of uniform spanning trees of dense graphs

    Eleanor Archer and Matan Shalev. The GHP scaling limit of uniform spanning trees of dense graphs. Random Structures Algorithms, 65(1):149–190, 2024

    work page 2024

  10. [10]

    Weak disorder asymptotics in the stochastic mean-field model of distance.Ann

    Shankar Bhamidi and Remco van der Hofstad. Weak disorder asymptotics in the stochastic mean-field model of distance.Ann. Appl. Probab., 22(1):29–69, 2012

    work page 2012

  11. [11]

    Fan Chung, Paul Horn, and L. Lu. Diameter of random spanning trees in a given graph.J. Graph Theory, 69(3):223–240, 2012

    work page 2012

  12. [12]

    Springer, Cham, 2017

    Francis Comets.Directed polymers in random environments, volume 2175 ofLecture Notes in Mathemat- ics. Springer, Cham, 2017. Lecture notes from the 46th Probability Summer School held in Saint-Flour, 2016

    work page 2017

  13. [13]

    Anatomy of a young giant component in the random graph.Random Structures Algorithms, 39(2):139–178, 2011

    Jian Ding, Jeong Han Kim, Eyal Lubetzky, and Yuval Peres. Anatomy of a young giant component in the random graph.Random Structures Algorithms, 39(2):139–178, 2011

    work page 2011

  14. [14]

    Maren Eckhoff, Jesse Goodman, Remco van der Hofstad, and Francesca R. Nardi. Short paths for first passage percolation on the complete graph.J. Stat. Phys., 151(6):1056–1088, 2013

    work page 2013

  15. [15]

    Maren Eckhoff, Jesse Goodman, Remco van der Hofstad, and Francesca R. Nardi. Long paths in first passage percolation on the complete graph II. Global branching dynamics.J. Stat. Phys., 181(2):364–447, 2020

    work page 2020

  16. [16]

    The scaling limits of the minimal spanning tree and invasion percolation in the plane.Ann

    Christophe Garban, Gábor Pete, and Oded Schramm. The scaling limits of the minimal spanning tree and invasion percolation in the plane.Ann. Probab., 46(6):3501–3557, 2018

    work page 2018

  17. [17]

    Uniform spanning forests of planar graphs.Forum Math

    Tom Hutchcroft and Asaf Nachmias. Uniform spanning forests of planar graphs.Forum Math. Sigma, 7:Paper No. e29, 55, 2019

    work page 2019

  18. [18]

    The diameter of random spanning trees interpolating between the UST and the MST of the complete graph.arXiv preprint arXiv:2410.18269, 2024

    Ágnes Kúsz. The diameter of random spanning trees interpolating between the UST and the MST of the complete graph.arXiv preprint arXiv:2410.18269, 2024. 36 L. MAKOWIEC, M. SAL VI, AND R. SUN

    work page arXiv 2024

  19. [19]

    Coupling from the past

    David A. Levin and Yuval Peres.Markov chains and mixing times. American Mathematical Society, Providence, RI, second edition, 2017. With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson

    work page 2017

  20. [20]

    Limits of dense graph sequences.J

    László Lovász and Balázs Szegedy. Limits of dense graph sequences.J. Combin. Theory Ser. B, 96(6):933–957, 2006

    work page 2006

  21. [21]

    Component behavior near the critical point of the random graph process.Random Structures Algorithms, 1(3):287–310, 1990

    Tomasz Łuczak. Component behavior near the critical point of the random graph process.Random Structures Algorithms, 1(3):287–310, 1990

    work page 1990

  22. [22]

    Cambridge University Press, New York, 2016

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

    work page 2016

  23. [23]

    Minimal spanning forests.Ann

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

    work page 2006

  24. [24]

    Local limits of random spanning trees in random environment

    Luca Makowiec. Local limits of random spanning trees in random environment. arXiv preprint arXiv:2410.16836, 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  25. [25]

    Observables of random spanning trees in random environment, 2025

    Luca Makowiec. Observables of random spanning trees in random environment, 2025. PhD Thesis. Work in progress

    work page 2025

  26. [26]

    Diameter of uniform spanning trees on random weighted graphs.arXiv:2311.01808, 2023

    Luca Makowiec, Michele Salvi, and Rongfeng Sun. Diameter of uniform spanning trees on random weighted graphs.arXiv:2311.01808, 2023. To appear in Annales de l’Institut Henri Poincaré Probabilités et Statistiques

    work page arXiv 2023

  27. [27]

    The diameter of uniform spanning trees in high dimensions

    Peleg Michaeli, Asaf Nachmias, and Matan Shalev. The diameter of uniform spanning trees in high dimensions. Probab. Theory Related Fields, 179(1-2):261–294, 2021

    work page 2021

  28. [28]

    Critical random graphs: diameter and mixing time.Ann

    Asaf Nachmias and Yuval Peres. Critical random graphs: diameter and mixing time.Ann. Probab., 36(4):1267–1286, 2008

    work page 2008

  29. [29]

    C. M. Newman and D. L. Stein. Ground-state structure in a highly disordered spin-glass model.J. Statist. Phys., 82(3-4):1113–1132, 1996

    work page 1996

  30. [30]

    Critical percolation and the minimal spanning tree in slabs

    Charles Newman, Vincent Tassion, and Wei Wu. Critical percolation and the minimal spanning tree in slabs. Comm. Pure Appl. Math., 70(11):2084–2120, 2017

    work page 2084

  31. [31]

    Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs

    Yuval Peres and David Revelle. Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs.ArXiv:math/0410430, 2005

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  32. [32]

    The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus.Probab

    Jason Schweinsberg. The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus.Probab. Theory Related Fields, 144(3-4):319–370, 2009

    work page 2009

  33. [33]

    Approximate counting, uniform generation and rapidly mixing Markov chains.Inform

    Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains.Inform. and Comput., 82(1):93–133, 1989

    work page 1989

  34. [34]

    Szekeres

    G. Szekeres. Distribution of labelled trees by diameter. InCombinatorial mathematics, X (Adelaide, 1982), volume 1036 ofLecture Notes in Math., pages 392–397. Springer, Berlin, 1983

    work page 1982

  35. [35]

    Cambridge University Press, Cambridge, 2018

    Roman Vershynin.High-dimensional probability, volume 47 ofCambridge Series in Statistical and Prob- abilistic Mathematics. Cambridge University Press, Cambridge, 2018. An introduction with applications in data science, With a foreword by Sara van de Geer

    work page 2018

  36. [36]

    Generating random spanning trees more quickly than the cover time

    David Bruce Wilson. Generating random spanning trees more quickly than the cover time. InProceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pages 296–303. ACM, New York, 1996. Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, 119076 Singapore Email address: makowi...

    work page 1996