Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane

2025/10/27 by Draganov, Ondřej, Edelsbrunner, Herbert, Rosenmeier, Sophie +1
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2510.23373

Abstract

Let c be the constant such that the expected length of the Euclidean minimum spanning tree of n random points in the unit square is c √(n) in the limit, when n goes to infinity. We improve the prior best lower bound of 0.6008 ≤ c by Avram and Bertsimas to 0.6289 ≤ c. The proof is a by-product of studying the persistent homology of randomly 2-colored point sets. Specifically, we consider the filtration induced by the inclusions of the two mono-chromatic sublevel sets of the Euclidean distance function into the bi-chromatic sublevel set of that function. Assigning colors randomly, and with equal probability, we show that the expected 1-norm of each chromatic persistence diagram is a constant times √(n) in the limit, and we determine the constant in terms of c and another constant, c_L, which arises for a novel type of Euclidean minimum spanning tree of 2-colored point sets.

Citations

• Two trees are better than one
• On the shape of a set of points in the plane
• On the shortest spanning subtree of a graph and the traveling salesman problem

Related

• Random Minimum Spanning Tree and Dense Graph Limits
• Minimum spanning acycle and lifetime of persistent homology in the Linial-Meshulam process
• On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
• The scaling limit of the minimum spanning tree of the complete graph
• On Minimum Spanning Trees for Random Euclidean Bipartite Graphs