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

28 May 2013
Christina Goldschmidt
Consider the complete graph on n vertices with independent and identically distributed edge-weights having some absolutely continuous distribution. The minimum spanning tree (MST) is simply the spanning subtree of smallest weight. It is straightforward to construct the MST using one of several natural algorithms. Kruskal's algorithm builds the tree edge by edge starting from the globally lowest-weight edge and then adding other edges one by one in increasing order of weight, as long as they do not create any cycles. At each step of this process, the algorithm has generated a forest, which becomes connected on the final step. In this talk, I will explain how it is possible to exploit a connection between the forest generated by Kruskal's algorithm and the Erd\"os-R\'enyi random graph in order to prove that $M_n$, the MST of the complete graph, possesses a scaling limit as $n$ tends to infinity. In particular, if we think of $M_n$ as a metric space (using the graph distance), rescale edge-lengths by $n^{-1/3}$, and endow the vertices with the uniform measure, then $M_n$ converges in distribution in the sense of the Gromov-Hausdorff-Prokhorov distance to a certain random measured real tree. This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).
  • Combinatorial Theory Seminar