EnglishFrançais

Site Web DMA

Bannière DMA Site de l'ENS Site Paris Sciences et Lettres Site du CNRS Accueil

Séminaire informel de Probabilités et Statistiques

Horaires : Le lundi 03 mars 2014, 11h-12h

Lieu : Salle W

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

Christina Goldschmidt (Oxford - page personnelle)

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 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).

 

Autres séances du séminaire


45 rue d'Ulm - F 75230 PARIS cedex 05 | phone : (33) 1 44 32 20 49 | fax : (33) 1 44 32 20 69

Plan du site | Mentions légales | | Edition du site | Web site designed under SPIP