Pure Mathematics Seminar: Christina Goldschmidt

Christina Goldschmidt, University of Oxford

Wednesday 08 May 2013, 1600-1700
A54, Postgraduate Statistics Centre Lecture Theatre

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 Mn, the MST of the complete graph, possesses a scaling limit as n tends to infinity. In particular, if we think of Mn as a metric space (using the graph distance), rescale edge-lengths by n-1/3, and endow the vertices with the uniform measure, then Mn converges in distribution to 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).