← 研踪 PaperTrailarXiv:2611.21540 · v1
The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph
完全图最小生成树中叶子权重之和
首次提交 2026-11-17 02:26
版本更新 2026-11-17 02:26
雷达观测 2026-11-17 16:10
摘要
Let be a random weighted complete graph on vertices, where edges have i.i.d. weights. Let be the Minimum Spanning Tree (MST) of . The expected weight of is known to converge to (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of , denoting this quantity by . We give tight upper and lower bounds on and determine its limit as diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of around 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).
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 02:26 · 最新观测版本
The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph
Let be a random weighted complete graph on vertices, where edges have i.i.d. weights. Let be the Minimum Spanning Tree (MST) of . The expected weight of is known to converge to (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of , denoting this quantity by . We give tight upper and lower bounds on and determine its limit as diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of around 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).
查看此版本解读 →查看此版本原文 ↗