pith. sign in

arxiv: 2410.16836 · v4 · pith:V67VSKK7new · submitted 2024-10-22 · 🧮 math.PR · math.CO

Local limits of random spanning trees in random environment

Luca Makowiec This is my paper

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

classification 🧮 math.PR math.CO
keywords random spanning treesrandom environmentlocal limitsedge overlapphase transitioncomplete graphminimum spanning tree
0
0 comments X

The pith

The RSTRE on K_n transitions from uniform spanning tree behavior to minimum spanning tree behavior as β grows past order n.

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

The paper analyzes the random spanning tree in random environment on the complete graph, where trees are chosen with probability proportional to exp(-β times the sum of random weights on the edges). For β much smaller than n over log n, the expected overlap with the minimum spanning tree is approximately β, and the local structure matches the uniform spanning tree. For β much larger than n log squared n, the overlap is nearly n, and the local structure matches the minimum spanning tree. The change in local limit occurs when β is around n. This shows the model interpolates between the two extremes depending on the scale of β relative to n.

Core claim

The RSTRE has edge overlap (1+o(1))β with the MST for β = o(n/log n) and (1-o(1))n for β ≫ n log² n. Its local limit equals the uniform spanning tree's for small β and the minimum spanning tree's for β > n log^λ n with λ→∞ arbitrarily slowly. The transition in local limit is located around β = n.

What carries the argument

The parameter β in the exponential weighting exp(-β ω_e) of i.i.d. uniform edge weights, which controls the bias toward lower-weight edges in the spanning tree distribution.

If this is right

  • The overlap increases linearly with β in the low regime.
  • The local limit is that of the UST when β = o(n/log n).
  • The local limit is that of the MST when β exceeds n times a slowly growing log power.
  • Edge overlap saturates at n for large β.

Where Pith is reading between the lines

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

  • In the window β of order n there may be an intermediate local limit.
  • The transition thresholds may depend on the specific weight distribution.
  • Similar phase transitions could be studied in sparse random graphs.

Load-bearing premise

The graph is the complete graph K_n and the weights are i.i.d. uniform on [0,1] with the exponential form of the weighting.

What would settle it

For n large and β = n, check if the local limit of the RSTRE differs from both the uniform and minimum spanning tree limits by examining the degree distribution or other local statistics.

read the original abstract

We study the edge overlap and local limit of the random spanning tree in random environment (RSTRE) on the complete graph with $n$ vertices and weights given by $\exp(-\beta \omega_e)$ for $\omega_e$ uniformly distributed on $[0,1]$. We show that for $\beta$ growing with $\beta = o(n/\log n)$, the edge overlap is $(1+o(1)) \beta$, while for $\beta$ much larger than $n \log^2 n$, the edge overlap is $(1-o(1))n$. Furthermore, there is a transition of the local limit around $\beta = n$. When $\beta = o(n/ \log n)$ the RSTRE locally converges to the same limit as the uniform spanning tree, whereas for $\beta$ larger than $n \log^\lambda n$, where $\lambda = \lambda(n) \rightarrow \infty$ arbitrarily slowly, the local limit of the RSTRE is the same as that of the minimum spanning tree.

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 / 1 minor

Summary. The manuscript studies edge overlap and local weak limits of the random spanning tree in random environment (RSTRE) on the complete graph K_n, with edge weights given by exp(-β ω_e) for i.i.d. uniform[0,1] weights ω_e. It claims that for β = o(n/log n) the edge overlap is (1+o(1))β while for β ≫ n log² n the overlap is (1-o(1))n; furthermore, the local limit transitions around β = n, coinciding with that of the uniform spanning tree for β = o(n/log n) and with that of the minimum spanning tree for β > n log^λ n where λ(n) → ∞ arbitrarily slowly.

Significance. If the stated regimes and transition are rigorously established, the work would provide a quantitative description of the interpolation between uniform and minimum spanning trees via the inverse-temperature parameter β. The explicit overlap asymptotics in the two extreme regimes constitute a concrete, falsifiable contribution to the literature on weighted spanning trees.

major comments (2)
  1. [Abstract] Abstract: the claim that 'there is a transition of the local limit around β = n' is not supported by the proven regimes. The UST-like local limit is established only for β = o(n/log n), while the MST-like limit requires β > n log^λ n (λ → ∞ arbitrarily slowly). This leaves an unanalyzed window of width roughly n/log n to n log^λ n that is load-bearing for the asserted transition scale; without results or heuristics inside this window the location of the transition remains conjectural.
  2. [Abstract] Abstract (overlap statements): the overlap result for large β is stated only for β ≫ n log² n, which is strictly stronger than the local-limit regime β > n log^λ n. It is therefore unclear whether the overlap statement (1-o(1))n holds throughout the local-limit regime or only in a sub-regime; this gap affects the consistency of the two sets of claims.
minor comments (1)
  1. [Abstract] The phrase 'λ = λ(n) → ∞ arbitrarily slowly' should be accompanied by an explicit statement of the admissible growth rates (e.g., log log n or slower) to make the regime precise.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments correctly identify gaps between the proven regimes and the abstract claims. We address each point below and will revise the abstract to align the stated claims precisely with the theorems.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that 'there is a transition of the local limit around β = n' is not supported by the proven regimes. The UST-like local limit is established only for β = o(n/log n), while the MST-like limit requires β > n log^λ n (λ → ∞ arbitrarily slowly). This leaves an unanalyzed window of width roughly n/log n to n log^λ n that is load-bearing for the asserted transition scale; without results or heuristics inside this window the location of the transition remains conjectural.

    Authors: We agree that the theorems leave an intermediate window unanalyzed and therefore do not rigorously locate the transition at scale β = n. The phrasing 'around β = n' was meant to convey that the change from UST-like to MST-like behavior occurs when β reaches order n (the lower regime being o(n/log n) and the upper regime beginning at n times a slowly diverging function). Since no results or heuristics are available inside the gap, the precise location is indeed conjectural. We will revise the abstract to state that the local limit transitions from the UST limit to the MST limit as β grows, with the transition occurring somewhere between the two proven regimes. revision: yes

  2. Referee: [Abstract] Abstract (overlap statements): the overlap result for large β is stated only for β ≫ n log² n, which is strictly stronger than the local-limit regime β > n log^λ n. It is therefore unclear whether the overlap statement (1-o(1))n holds throughout the local-limit regime or only in a sub-regime; this gap affects the consistency of the two sets of claims.

    Authors: The referee is correct that the overlap claim (1-o(1))n is proven only under the stronger condition β ≫ n log² n. The local-limit result holds under the weaker condition β > n log^λ n, but the overlap proof requires the extra logarithmic factor for technical reasons (concentration estimates). We currently have no argument showing that overlap reaches (1-o(1))n already at the local-limit threshold. We will revise the abstract to state the overlap results with their exact conditions and to separate them clearly from the local-limit statements, thereby removing any implication that the two sets of claims apply to identical regimes. revision: yes

Circularity Check

0 steps flagged

No circularity; asymptotic claims are model-derived without reduction to inputs

full rationale

The paper defines the RSTRE on K_n with i.i.d. uniform[0,1] weights and exponential reweighting exp(-β ω_e), then states asymptotic overlap and local-limit results in explicit regimes of β(n) as n→∞. No step equates a derived quantity to a fitted parameter by construction, renames a known pattern, or loads the central transition claim on a self-citation whose content is itself unverified. The regimes are stated directly from the model; the gap between o(n/log n) and n log^λ n is a question of proof coverage, not circularity. The derivation chain remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper works in the standard setting of probability on graphs with i.i.d. uniform weights; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • standard math Standard asymptotic analysis on the complete graph K_n as n→∞
    Invoked implicitly when stating o(1) and (1+o(1)) statements for β(n) regimes.

pith-pipeline@v0.9.0 · 5695 in / 1229 out tokens · 18205 ms · 2026-05-23T19:07:59.273696+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. Random spanning trees in random environment

    math.PR 2024-10 unverdicted novelty 7.0

    RSTRE model on K_n with i.i.d. uniform disorders exhibits diameter n^{1/2} for β ≤ C n/log n and n^{1/3} for β ≥ n^{4/3} log n, with conjecture for intermediate exponents.

Reference graph

Works this paper leans on

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

  1. [1]

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

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

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  2. [2]

    Recurrence of distribu tional limits of finite planar graphs

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

    work page 2001

  3. [3]

    Modern graph theory , volume 184 of Graduate Texts in Mathematics

    Béla Bollobás. Modern graph theory , volume 184 of Graduate Texts in Mathematics . Springer-Verlag, New York, 1998

    work page 1998

  4. [4]

    Local characteristic s, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances

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

    work page 1993

  5. [5]

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

    work page 1985

  6. [6]

    G. R. Grimmett. Random labelled trees and their branchin g networks. J. Austral. Math. Soc. Ser. A , 30(2):229–237, 1980

    work page 1980

  7. [7]

    On the cover time for random walks on rand om graphs

    Johan Jonasson. On the cover time for random walks on rand om graphs. Combin. Probab. Comput. , 7(3):265–279, 1998

    work page 1998

  8. [8]

    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 interp olating between the UST and the MST of the complete graph. arXiv preprint arXiv:2410.18269 , 2024

    work page arXiv 2024

  9. [9]

    Component behavior near the critical poi nt of the random graph process

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

    work page 1990

  10. [10]

    Probability on trees and networks , volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics

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

    work page 2016

  11. [11]

    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

  12. [12]

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

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

    work page arXiv 2023

  13. [13]

    Random spanning trees in random environment

    Luca Makowiec, Michele Salvi, and Rongfeng Sun. Random spanning trees in random environment. arXiv preprint arXiv:2410.16830 , 2024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  14. [14]

    The local limit of unifor m spanning trees

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

    work page 2022

  15. [15]

    Random graphs and complex networks

    Remco van der Hofstad. Random graphs and complex networks. Vol. 1 , volume [43] of Cambridge Series in Statistical and Probabilistic Mathematics . Cambridge University Press, Cambridge, 2017. Depar tment of Ma thema tics, Na tional University of Singapo re, 10 Lower Kent Ridge Road, 119076 Singapore Email address : makowiec@u.nus.edu

    work page 2017