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

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ö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 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.
Type de document :
Article dans une revue
Annals of Probability, Institute of Mathematical Statistics, 2017, 45, pp.3075--3144
Liste complète des métadonnées

https://hal.inria.fr/hal-00773360
Contributeur : Nicolas Broutin <>
Soumis le : dimanche 13 janvier 2013 - 15:59:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

  • HAL Id : hal-00773360, version 1
  • ARXIV : 1301.1664

Collections

Citation

Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt, Grégory Miermont. The scaling limit of the minimum spanning tree of the complete graph. Annals of Probability, Institute of Mathematical Statistics, 2017, 45, pp.3075--3144. 〈hal-00773360〉

Partager

Métriques

Consultations de la notice

279