Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912672538165248 |
|---|---|
| author | Draganov, Ondřej Edelsbrunner, Herbert Rosenmeier, Sophie Saghafian, Morteza |
| author_facet | Draganov, Ondřej Edelsbrunner, Herbert Rosenmeier, Sophie Saghafian, Morteza |
| contents | 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 \leq c$ by Avram and Bertsimas to $0.6289 \leq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_23373 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane Draganov, Ondřej Edelsbrunner, Herbert Rosenmeier, Sophie Saghafian, Morteza Probability Computational Geometry Combinatorics 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 \leq c$ by Avram and Bertsimas to $0.6289 \leq 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. |
| title | Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane |
| topic | Probability Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2510.23373 |