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

Abstract

The global structure of the minimal spanning tree (MST) is expected to be universal for a large class of underlying random discrete structures. However, very little is known about the intrinsic geometry of MSTs of most standard models, and so far the scaling limit of the MST viewed as a metric measure space has only been identified in the case of the complete graph [5]. In this work, we show that the MST constructed by assigning i.i.d. continuous edge-weights to either the random (simple) $3$-regular graph or the $3$-regular configuration model on $n$ vertices, endowed with the tree distance scaled by $n^{-1/3}$ and the uniform probability measure on the vertices, converges in distribution with respect to Gromov-Hausdorff-Prokhorov topology to a random compact metric measure space. Further, this limiting space has the same law as the scaling limit of the MST of the complete graph identified in [5] up to a scaling factor of $6^{1/3}$. Our proof relies on a novel argument that proceeds via a comparison between a $3$-regular configuration model and the largest component in the critical Erdős-Rényi random graph. The techniques of this paper can be used to establish the scaling limit of the MST in the setting of general random graphs with given degree sequences provided two additional technical conditions are verified.

arXiv comment61 pages; to appear in Probability Theory and Related Fields

References in corpus (14)

• Random trees and applications
• Optimal Paths in Disordered Complex Networks
• A note on Gromov-Hausdorff-Prokhorov distance between (locally) compact measure spaces
• Critical random graphs: Diameter and mixing time
• The phase transition in the configuration model
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Scaling Limits for Minimal and Random Spanning Trees in Two Dimensions
• Minimal spanning forests
• The coding of compact real trees by real valued functions
• The local weak limit of the minimum spanning tree of the complete graph
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• A probabilistic approach to the leader problem in random graphs
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps

Cited by in corpus (3)

• A probabilistic approach to the leader problem in random graphs
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps
• The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights