Minimum spanning tree leaf edges weights converge with new bounds

The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph

Discrete Mathematics

Summary

When you connect points using the cheapest possible connections, you get what's called a minimum spanning tree. The paper studies how the total cost of edges touching the 'end' points (or leaves) behaves as the number of points grows large. The authors find precise limits and show that the leaf edge costs don’t vary much from these limits. Their findings also improve understanding of two challenging variations of this cheap-connection problem.

What this means in practice

  • For network design engineers: Improve design cost bounds for connecting terminals in random network topologies using better Steiner tree weight estimates.
  • For logistics planners: Enhance probabilistic route optimization by leveraging tighter upper bounds for stochastic minimum spanning tree models.

A theory result. No direct application yet.

Authors

Julia Gaudio, Phawin Prongpaophan, Miklós Z. Rácz

Abstract

Let $G_n$ be a random weighted complete graph on $n$ vertices, where edges have i.i.d. $\text{Unif}(0,1)$ weights. Let $T_n$ be the Minimum Spanning Tree (MST) of $G_n$. The expected weight of $T_n$ is known to converge to $ζ(3) = \sum_{k=1}^{\infty} \frac{1}{k^3}$ (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of $T_n$, denoting this quantity by $L_n$. We give tight upper and lower bounds on $\mathbb{E}[L_n]$ and determine its limit as $n$ diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of $L_n$ around $\mathbb{E}[L_n]$ and almost sure convergence to this value. These results directly yield substantial improvements to state-of-the-art bounds for two important variants of the MST problem: (1) an improved upper bound on the weight of the optimal random instance Steiner tree, as studied by Bollobás, Gamarnik, Riordan, and Sudakov (2004); and (2) an improvement over the upper bound for the Probabilistic Minimum Spanning Tree, introduced by Bertsimas (1988).