Probabilistic aspects of minimum spanning trees

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.

Speaker Details

Louigi Addario-Berry is an assistant professor at McGill University. Previously, he held an assistant professorship at Université de Montreal and a Marie Curie research fellowship at the University of Oxford. http://www.math.mcgill.ca/louigi/

Series:
Microsoft Research Talks
Date:
Speakers:
Louigi Addario-Berry
Affiliation:
McGill University

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks