Speaker Louigi Addario-Berry
Affiliation McGill University
Host Yuval Peres
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.
People also watched
Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives