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

Consider the complete graph on n vertices with independent andidentically distributed edge-weights having some absolutely continuousdistribution. The minimum spanning tree (MST) is simply the spanningsubtree of smallest weight. It is straightforward to construct theMST using one of several natural algorithms. Kruskal’s algorithmbuilds the tree edge by edge starting from the globally lowest-weightedge and then adding other edges one by one in increasing order ofweight, as long as they do not create any cycles. At each step of thisprocess, the algorithm has generated a forest, which becomes connectedon the final step. In this talk, I will explain how it is possible toexploit a connection between the forest generated by Kruskal’salgorithm and the Erdös-Rényi random graph in order to prove that M_n,the MST of the complete graph, possesses a scaling limit as n tends toinfinity. In particular, if we think of M_n as a metric space (usingthe graph distance), rescale edge-lengths by n^{-1/3}, and endow thevertices with the uniform measure, then M_n converges in distributionin the sense of the Gromov-Hausdorff-Prokhorov distance to a certainrandom measured real tree.This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin(INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).