Ultrametric spaces and clouds

Abstract

In ``Characterization, stability and convergence of hierarchical clustering methods'' by G. E. Carlsson, F. Memoli, the natural way to construct an ultrametric space from a given metric space was presented. It was shown that the corresponding map $\text{U}$ is $1$-Lipschitz for every pair of bounded metric spaces, with respect to the Gromov-Hausdorff distance. We make a simple observation that $\text{U}$ is $1$-Lipschitz for pairs of all, not necessarily bounded, metric spaces. We then study the properties of the mapping $\text{U}$. We show that, for a given dotted connected metric space $A$, the mapping $\hat{I}¨:X\mapsto X\times A$ from the proper class of all bounded ultrametric spaces ($X\times A$ is endowed with the Manhattan metric) preserves the Gromov-Hausdorff distance. Moreover, the mapping $\text{U}$ is inverse to $\hat{I}¨$. By a dotted connected metric space, we mean a metric space in which for an arbitrary $\epsilon >0$ and every two points $p,q$, there exist points $x_0=p,x_1,\dots ,x_n=q$ such that ${\max }_{0\le j\le n-1}|x_j{x}_{j+1}|\le \epsilon$. At the end of the paper, we prove that each class (proper or not) consisting of unbounded metric spaces on finite Gromov-Hausdorff distances from each other cannot contain an ultrametric space and a dotted connected space simultaneously.

10 pages