Journal title
Annals of Probability
DOI
10.1214/16-AOP1132
Issue
5
Volume
45
Last updated
2022-03-08T05:10:37.31+00:00
Page
3075-3144
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 → ∞ to a random compact measured metric space in the Gromov–Hausdorff–Prokhorov topology. We additionally show that the limit is a random binary Rtree 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 in [4], 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 R-graphs, which generalise R-trees, and are of independent interest.
Symplectic ID
627635
Submitted to ORA
On
Publication type
Journal Article
Publication date
23 September 2017