Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; Miermont, Grégory The scaling limit of the minimum spanning tree of the complete graph. (English) Zbl 1407.60013 Ann. Probab. 45, No. 5, 3075-3144 (2017). Summary: 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\rightarrow \infty\) to a random compact measured metric space in the Gromov-Hausdorff-Prokhorov topology. We additionally show that the limit is a random binary \(\mathbb{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ős-Rényi random graph. We exploit the explicit description of the scaling limit of the Erdős-Rényi random graph in the so-called critical window, established in [the first author et al., Probab. Theory Relat. Fields 152, No. 3–4, 367–406 (2012; Zbl 1239.05165)], and provide a similar description of the scaling limit for a “critical minimum spanning forest” contained within the MST. In order to accomplish this, we introduce the notion of \(\mathbb{R}\)-graphs, which generalise \(\mathbb{R}\)-trees, and are of independent interest. Cited in 1 ReviewCited in 37 Documents MSC: 60C05 Combinatorial probability 60F05 Central limit and other weak theorems 05C80 Random graphs (graph-theoretic aspects) Keywords:minimum spanning tree; scaling limit; R-tree; R-graph; Gromov-Hausdorff-Prokhorov distance; critical random graphs Citations:Zbl 1239.05165 PDFBibTeX XMLCite \textit{L. Addario-Berry} et al., Ann. Probab. 45, No. 5, 3075--3144 (2017; Zbl 1407.60013) Full Text: DOI arXiv Euclid