Journal article

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 → ∞ 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.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Addario-Berry, L., Broutin, N., Goldschmidt, C., & Miermont, G. (2017). The scaling limit of the minimum spanning tree of the complete graph. Annals of Probability, 45(5), 3075–3144.

MLA Style

Addario-Berry, L., et al. “The Scaling Limit of the Minimum Spanning Tree of the Complete Graph.” Annals of Probability, vol. 45, no. 5, 2017, pp. 3075–144.

Chicago Style

Addario-Berry, L., N. Broutin, C. Goldschmidt, and G. Miermont. 2017. “The Scaling Limit of the Minimum Spanning Tree of the Complete Graph.” Annals of Probability 45 (5): 3075–144.
Print

Access Document

Files:: euclid.aop.1506132034.pdf

(Preview, Version of record, pdf, 811.0KB, Terms of use)

Publisher copy:: 10.1214/16-AOP1132

Authors

+ Addario-Berry, L More by this author

Role:: Author

+ Broutin, N More by this author

Role:: Author

+ Goldschmidt, C More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Statistics
Role:: Author

+ Miermont, G More by this author

Role:: Author

+ Royal Society More from this funder

Funding agency for:: Goldschmidt, C
Grant:: EP/N004833/1

+ Universite Paris-Sud More from this funder

Funding agency for:: Goldschmidt, C
Grant:: EP/N004833/1

+ Engineering and Physical Sciences Research Council More from this funder

Funding agency for:: Goldschmidt, C
Grant:: EP/N004833/1

Publisher:: Institute of Mathematical Statistics
Journal:: Annals of Probability More from this journal
Volume:: 45
Issue:: 5
Pages:: 3075-3144
Publication date:: 2017-09-23
Acceptance date:: 2016-06-13
DOI:: 10.1214/16-AOP1132
ISSN:: 0091-1798

Pubs id:: pubs:627635
UUID:: uuid:1668994b-0e8a-4303-9c22-c566101f0f00
Local pid:: pubs:627635
Source identifiers:: 627635
Deposit date:: 2016-06-13
ARK identifier:: ark:/29072/ora_1668994b0e8a43039c22c566101f0f00

Terms of use

Copyright holder:: Institute of Mathematical Statistics
Copyright date:: 2017
Notes:: © Institute of Mathematical Statistics, 2017.

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

Views and downloads will return soon

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP