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

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\sqrt{n}$ in the limit, when $n$ goes to infinity. We improve the prior best lower bound of $0.6008\le c$ by Avram and Bertsimas to $0.6289\le 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 $\sqrt{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.

14 pages. AATRN seminar talk about the paper: http://youtu.be/tl-UwQksE3E?si=e8VNdRhmGv4-ytXt