# zbMATH — the first resource for mathematics

The scaling limit of the minimum spanning tree of the complete graph. (English) Zbl 1407.60013
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.

##### MSC:
 60C05 Combinatorial probability 60F05 Central limit and other weak theorems 05C80 Random graphs (graph-theoretic aspects)
Full Text: