Probabilistic aspects of minimum spanning trees

Опубликовано 27 июля 2016, 19:31

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