Christina Goldschmidt (University of Oxford)
21 March 2014 @ 11:00
- Past event
The scaling limit of the minimum spanning tree of the complete graph
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ö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 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 a certain random real tree.
This is joint work with Louigi Addario-Berry (McGill), Nicolas Broutin (INRIA Paris-Rocquencourt) and Grégory Miermont (ENS Lyon).