Probabilistic aspects of minimum spanning trees

Speaker  Louigi Addario-Berry

Affiliation  McGill University

Host  Yuval Peres

Duration  00:56:23

Date recorded  17 April 2013

Give the edges of the complete graph Kn independent uniformly distributed edge weights, and let Mn be the resulting minimum spanning tree. What can be said about the structure of Mn? A classic result of Alan Frieze is that the total weight of Mn converges to zeta(3) as n--infinity. We rather focus on the metric space structure of Mn, bounding its diameter and discussing its graph-theoretic distributional properties. In particular, we will outline a proof that Mn typically has diameter of order the cube root of n; this in particular distinguishes Mn from a uniformly random spanning tree of Kn, which has typical diameter of order the square root of n.

©2013 Microsoft Corporation. All rights reserved.
> Probabilistic aspects of minimum spanning trees