完全图最小生成树中叶子权重之和
The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph
Julia Gaudio, Phawin Prongpaophan, Miklós Z. Rácz
AI 速读 基于摘要
研究随机加权完全图的最小生成树中与叶子关联的边权重之和,确定其期望极限并证明集中性,进而改进Steiner树和概率最小生成树问题的上界。
cs.DM · math.CO
查看原文摘要
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).