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

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.

arXiv comment39 pages, 1 figure

References in corpus (8)

• Random trees and applications
• A note on Gromov-Hausdorff-Prokhorov distance between (locally) compact measure spaces
• Scaling Limits for Minimal and Random Spanning Trees in Two Dimensions
• Minimal spanning forests
• Relations between invasion percolation and critical percolation in two dimensions
• Component sizes of the random graph outside the scaling window
• Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs
• The scaling limit of the Minimal Spanning Tree - a preliminary report

Cited by in corpus (14)

• Critical window for the configuration model: finite third moment degrees
• The gap between Gromov-vague and Gromov-Hausdorff-vague topology
• Heavy-tailed configuration models at criticality
• Distances in critical long range percolation
• The dual tree of a recursive triangulation of the disk
• Long paths in first passage percolation on the complete graph I. Local PWIT dynamics
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Minimal spanning trees and Stein's method
• Geometry of the minimal spanning tree of a random $3$-regular graph
• Scaling limits of stochastic processes associated with resistance forms
• Convex minorant trees associated with Brownian paths and the continuum limit of the minimum spanning tree
• Continuum limit of critical inhomogeneous random graphs
• Scaling limits for some random trees constructed inhomogeneously
• Continuum random tree as the scaling limit for a drainage network model: a Brownian web approach