THE SCALING LIMIT OF THE MINIMUM SPANNING TREE OF THE COMPLETE GRAPH

• 成果类型: Article
• 署名作者: Addario-Berry, Louigi; Broutin, Nicolas; Goldschmidt, Christina; Miermont, Gregory
• 署名单位: McGill University; University of Oxford; University of Oxford; Ecole Normale Superieure de Lyon (ENS de LYON)
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/16-AOP1132
• 发表日期: 2017
• 页码: 3075-3144
• 关键词: invasion percolation; Combinatorial Optimization; THEOREM; GROWTH; length; asymptotics; HISTORY

摘要

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 -> infinity to a random compact 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 resealed version thereof. Our approach relies on a coupling between the MST problem and the Erdos-Renyi random graph. We exploit the explicit description of the scaling limit of the Erdos-Renyi random graph in the so-called critical window, established in [Probab. Theory Related Fields 152 (2012) 367-406], 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.