pith. sign in

arxiv: 1301.1664 · v1 · pith:GAOOJO6Unew · submitted 2013-01-08 · 🧮 math.PR · math.CO

The scaling limit of the minimum spanning tree of the complete graph

classification 🧮 math.PR math.CO
keywords randomgraphlimittreeminimumscalingspanningcomplete
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.