Séminaire du 5 decembre 05 : Nicolas Broutin, McGill University, Montreal, Canada.
The diameter of the Minimal Spanning Tree of the Complete Graph
Let the complete graph K_n be weighted with i.i.d. [0,1]-uniform random variables. Build the minimum spanning tree T of this graph. Many properties of T are well understood, in particular the degrees (Aldous), the egde lengths (Penrose) and the overall weight (Frieze). Most of them can be captured using only local arguments. We are interested in a global parameter, the diameter of T. We prove that its expected value is of order n^{1/3}. The proof relies on the connection with Erdos-Renyi G_{n,p} random graphs. We use the classical branching process construction of G_{n,p}. In particular a careful analysis of the critical window is necessary. We also use concentration properties of various random walks and the height of uniformly chosen rooted trees.
(with L. Addario-Berry and B. Reed).
Virginie Collette
Last modified: Mon May 23 18:32:54 CEST 2005