Subtree Distances, Tight Spans and Diversities
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913985164476416 |
|---|---|
| author | Bryant, David Huber, Katharina T. Moulton, Vincent Spillner, Andreas |
| author_facet | Bryant, David Huber, Katharina T. Moulton, Vincent Spillner, Andreas |
| contents | Metric embeddings are central to metric theory and its applications. Here we consider embeddings of a different sort: maps from a set to subsets of a metric space so that distances between points are approximated by minimal distances between subsets. Our main result is a characterization of when a set of distances $d(x,y)$ between elements in a set $X$ have a subtree representation, a real tree $T$ and a collection $\{S_x\}_{x \in X}$ of subtrees of~$T$ such that $d(x,y)$ equals the length of the shortest path in~$T$ from a point in $S_x$ to a point in $S_y$ for all $x,y \in X$. The characterization was first established for {\em finite} $X$ by Hirai (2006) using a tight span construction defined for distance spaces, metric spaces without the triangle inequality. To extend Hirai's result beyond finite $X$ we establish fundamental results of tight span theory for general distance spaces, including the surprising observation that the tight span of a distance space is hyperconvex. We apply the results to obtain the first characterization of when a diversity -- a generalization of a metric space which assigns values to all finite subsets of $X$, not just to pairs -- has a tight span which is tree-like. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13202 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Subtree Distances, Tight Spans and Diversities Bryant, David Huber, Katharina T. Moulton, Vincent Spillner, Andreas Metric Geometry Discrete Mathematics Populations and Evolution 05C12, 54E35 Metric embeddings are central to metric theory and its applications. Here we consider embeddings of a different sort: maps from a set to subsets of a metric space so that distances between points are approximated by minimal distances between subsets. Our main result is a characterization of when a set of distances $d(x,y)$ between elements in a set $X$ have a subtree representation, a real tree $T$ and a collection $\{S_x\}_{x \in X}$ of subtrees of~$T$ such that $d(x,y)$ equals the length of the shortest path in~$T$ from a point in $S_x$ to a point in $S_y$ for all $x,y \in X$. The characterization was first established for {\em finite} $X$ by Hirai (2006) using a tight span construction defined for distance spaces, metric spaces without the triangle inequality. To extend Hirai's result beyond finite $X$ we establish fundamental results of tight span theory for general distance spaces, including the surprising observation that the tight span of a distance space is hyperconvex. We apply the results to obtain the first characterization of when a diversity -- a generalization of a metric space which assigns values to all finite subsets of $X$, not just to pairs -- has a tight span which is tree-like. |
| title | Subtree Distances, Tight Spans and Diversities |
| topic | Metric Geometry Discrete Mathematics Populations and Evolution 05C12, 54E35 |
| url | https://arxiv.org/abs/2501.13202 |