The scaling limit of the minimum spanning tree of the complete graph
From MaRDI portal
Abstract: Consider the minimum spanning tree (MST) of the complete graph with n vertices, when edges are assigned independent random weights. Endow this tree with the graph distance renormalized by n^{1/3} and with the uniform measure on its vertices. We show that the resulting space converges in distribution, as n tends to infinity, to a random measured metric space in the Gromov-Hausdorff-Prokhorov topology. We additionally show that the limit is a random binary R-tree and has Minkowski dimension 3 almost surely. In particular, its law is mutually singular with that of the Brownian continuum random tree or any rescaled version thereof. Our approach relies on a coupling between the MST problem and the Erd"os-R'enyi random graph. We exploit the explicit description of the scaling limit of the Erd"os-R'enyi random graph in the so-called critical window, established by the first three authors in an earlier paper, and provide a similar description of the scaling limit for a "critical minimum spanning forest" contained within the MST.
Recommendations
- Geometry of the minimal spanning tree of a random 3-regular graph
- Critical random graphs and the structure of a minimum spanning tree
- Probability on a complete graph: uniform and minimal spanning trees
- The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
- On the value of a random minimum spanning tree problem
Cited in
(53)- The scaling limits of the minimal spanning tree and invasion percolation in the plane
- Scaling limits of stochastic processes associated with resistance forms
- The local limit of the uniform spanning tree on dense graphs
- The hyperbolic Brownian plane
- Critical random graphs and the differential equations technique
- Scaling limits for some random trees constructed inhomogeneously
- Asymptotics of integrals of Betti numbers for random simplicial complex processes
- Geometry of the minimal spanning tree of a random 3-regular graph
- Scaling limits of multi-type Markov branching trees
- Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
- A greedy algorithm for finding maximum spanning trees in infinite graphs
- The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
- Zooming in at the root of the stable tree
- Metrization of the Gromov-Hausdorff (-Prokhorov) topology for boundedly-compact metric spaces
- Universality for critical heavy-tailed network models: metric structure of maximal components
- Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
- Long paths in first passage percolation on the complete graph II. Global branching dynamics
- Heavy-tailed configuration models at criticality
- Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
- Invariance principles for random walks in random environment on trees
- The eternal multiplicative coalescent encoding via excursions of Lévy-type processes
- The dual tree of a recursive triangulation of the disk
- Noise sensitivity of critical random graphs
- Scaling limits of random trees and random graphs
- scientific article; zbMATH DE number 5730481 (Why is no real title available?)
- scientific article; zbMATH DE number 1123757 (Why is no real title available?)
- Partition functions of discrete coalescents: from Cayley's formula to Frieze's (3) limit theorem
- A probabilistic approach to the leader problem in random graphs
- On breadth‐first constructions of scaling limits of random graphs and random unicellular maps
- Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
- Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
- Stable graphs: distributions and line-breaking construction
- Scaling Limits of Markov-Branching Trees and Applications
- Parking on Cayley trees and frozen Erdős-Rényi
- Multisource invasion percolation on the complete graph
- Models of random subtrees of a graph
- A unified framework for generalizing the Gromov-Hausdorff metric
- Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
- The wired minimal spanning forest on the Poisson-weighted infinite tree
- Invasion percolation on power-law branching processes
- Scaling limit of critical random trees in random environment
- Minimum spanning trees in infinite graphs: theory and algorithms
- The GHP scaling limit of uniform spanning trees of dense graphs
- Epidemics on critical random graphs with heavy-tailed degree distribution
- The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
- Continuum limit of critical inhomogeneous random graphs
- Minimum spanning trees of random geometric graphs with independent edge weights
- Random minimum spanning tree and dense graph limits
- Noise sensitivity of the minimum spanning tree of the complete graph
- Scaling limits and universality: critical percolation on weighted graphs converging to an L^3 graphon
- Convergence of the height process of supercritical Galton-Watson forests with an application to the configuration model in the critical window
- The scaling limit of the root component in the wired minimal spanning forest of the Poisson weighted infinite tree
- The gap between Gromov-Vague and Gromov-Hausdorff-vague topology
This page was built for publication: The scaling limit of the minimum spanning tree of the complete graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1681600)
