pith. sign in

arxiv: 1301.1667 · v2 · pith:G5HLEIYSnew · submitted 2013-01-08 · 🧮 math.PR · math.CO

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

classification 🧮 math.PR math.CO
keywords treegrowthminimumpwitspanningvolumecompletegraph
0
0 comments X
read the original abstract

Assign i.i.d. standard exponential edge weights to the edges of the complete graph K_n, and let M_n be the resulting minimum spanning tree. We show that M_n converges in the local weak sense (also called Aldous-Steele or Benjamini-Schramm convergence), to a random infinite tree M. The tree M may be viewed as the component containing the root in the wired minimum spanning forest of the Poisson-weighted infinite tree (PWIT). We describe a Markov process construction of M starting from the invasion percolation cluster on the PWIT. We then show that M has cubic volume growth, up to lower order fluctuations for which we provide explicit bounds. Our volume growth estimates confirm recent predictions from the physics literature, and contrast with the behaviour of invasion percolation on the PWIT and on regular trees, which exhibit quadratic volume growth.

This paper has not been read by Pith yet.

discussion (0)

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

Forward citations

Cited by 2 Pith papers

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

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

    math.PR 2026-05 unverdicted novelty 7.0

    A new connection between second moments and pairwise negative correlation proves the p-NC property for minimal spanning trees and shows that the second moment of degrees in uniform spanning trees on finite connected r...

  2. 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.