Metric Space Recognition by Gromov–Hausdorff Distances to Simplexes
A. O. Ivanov, E. S. Lychagina, A. A. Tuzhilin · 2024
Read Metric Space Recognition by Gromov–Hausdorff Distances to Simplexes by A. O. Ivanov, E. S. Lychagina, A. A. Tuzhilin (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18949.txt.
Introduction
Ivanov and co-authors ask whether a metric space can be identified by its distances to the simplest possible spaces, in a 2024 paper. The test spaces are simplexes, where every pair of points sits at one same nonzero distance. The yardstick is the Gromov-Hausdorff distance, the standard way to compare shapes up to stretching. Some different spaces sit at zero distance and so can never be told apart.
The surprise: some spaces at positive distance from each other still produce identical distance lists to all simplexes. The authors exhibit such indistinguishable pairs. They then prove conditions, both sufficient and necessary, for when this blindness occurs. The paper maps a subtle limit of a widely used recognition idea.
Catalog record
| CREATOR | A. O. Ivanov, E. S. Lychagina, A. A. Tuzhilin |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-18949
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Metric Space Recognition by Gromov–Hausdorff Distances to Simplexes A. O. Ivanov, E. S. Lychagina, A. A. Tuzhilin Abstract In the present paper a distinguishability of bounded metric spaces by the set of the Gromov–Hausdorff distances to so-called simplexes (metric spaces with unique non-zero distance) is investigated. It is easy to construct an example of non-isometric metric spaces such that the Gromov–Hausdorff distance between them vanishes. Such spaces are non-distinguishable, of course. But we give examples of non-distinguishable metric spaces, the Gromov–Hausdorff distance between which is non-zero. More over, we prove several sufficient and necessary conditions for metric spaces to be non-distinguishable. Keywords: metric space, ultrametric space, minimal spanning tree, graph chromatic number, graph clique covering number, Borsuk’s number, Hausdorff distance, Gromov–Hausdorff distance, one-distance metric space 1 Introduction Modern computer graphics, image comparison and recognition systems, which are actively developing at present, often use so-called “spaces of spaces”. In addition to these applications, these spaces have a theoretical significance, and therefore continue to attract the attention of specialists in pure and applied mathematics. One of the possible approaches to the study of such spaces is based on construction of a distance function between spaces as a “measure of their dissimilarity”. In 1914, F. Hausdorff [ 1 ] introduced a non-negative symmetric function on pairs of non-empty subsets of a metric space X , equal to the greatest lower bound of such numbers r that one set is contained in the r -neighborhood of the other and vice versa. This function turned out to be a metric on the space of closed bounded subsets of X . Later, in 1975, D. Edwards [ 2 ] and, independently, in 1981, M. Gromov [ 3 ] generalized the Hausdorff construction to the family of all metric compacta, using their isometric embeddings into all possible ambient spaces (see the definition below). The resulting function is called the Gromov–Hausdorff distance, and the corresponding metric space of metric compacta, considered up to isometry, is called the Gromov–Hausdorff space and is denoted by {\cal M} . The geometry of this space turns out to be rather bizarre and is actively studied. It is well known that {\cal M} is a complete, separable, geodesic space, and also that {\cal M} is not proper [ 4 , 5 ] . The structure of the Gromov–Hausdorff space became the subject of the present paper. Pursuing the idea of “introducing coordinates in the space {\cal M} ”, a family of metric spaces with one non-zero distance, which we will call simplexes, was proposed for the role of coordinate axes. More precisely, each axis is a set of simplexes of fixed cardinality (but different diameters), and a metric compact is associated with a set of distance functions from it to the points of the axis. The problem of calculating the Gromov–Hausdorff distance between arbitrary metric spaces is quite nontrivial, therefore this choice of coordinate axes is due to the relative simplicity of such distance functions, a detailed study of which is given in [ 6 ] . In the paper [ 7 ] an example of two finite metric spaces that do not differ in distances to finite simplexes was given (see also below). From the results of [ 6 ] it immediately follows that the distances from these spaces to all possible simplexes are the same. The question arises: which spaces can be distinguished from each other in this way? We will give a number of necessary and sufficient conditions for the indistinguishability of spaces. We will show that the cardinalities of finite indistinguishable spaces must coincide. An example of a finite and a continuum indistinguishable spaces will be given, as well as a series of examples of indistinguishable spaces among which there are pairs of all possible cardinalities not less than the continuum. 2 Preliminaries Let us recall the necessary concepts and results concerning the Hausdorff and Gromov–Hausdorff distances. More detailed information can be found in [ 4 ] . Let X be an arbitrary non-empty set. Denote by \#X the cardinality of X . If X is a metric space and x and y are its points, then by |xy| we denote the distance between these points, and if A and B are non-empty subsets of X , then we set |AB|=|BA|=\inf\bigl\{|ab|:a\in A,\,b\in B\bigr\} . If A=\{a\} , then instead of \bigl|\{a\}B\bigr|=\bigl|B\{a\}\bigr| we write |aB|=|Ba| . For a metric space X , a point x\in X and a real number r>0 , by U_{r}(x) we denote the open ball with center at x and radius r , and for a non-empty subset A\subset X its r -neighborhood is defined as follows: U_{r}(A)=\big\{x\in X:|Ax|<r\big\}=\cup_{a\in A}U_{r}(a). Let X be a set. By {\cal P}_{0}(X) we denote the family of all its non-empty subsets. Further, let X be a metric space, and A,B\in{\cal P}_{0}(X) . The value d_{H}(A,B)=\inf\bigl\{r\in[0,\infty]:A\subset U_{r}(B)\quad\text{and}\quad U_{r}(A)\supset B\bigr\} is called the Hausdorff distance between A and B . It is well-known that d_{H} is a metric on the set {\cal H}(X) of all non-empty closed bounded subsets of the metric space X . Further, let X and Y be metric spaces. A triple (X^{\prime},Y^{\prime},Z) consisting of a metric space Z and its two subsets X^{\prime} and Y^{\prime} that are isometric to X and Y , respectively, is called a realization of the pair (X,Y) . The greatest lower bound d_{GH}(X,Y) of reals r such that there exists a realization (X^{\prime},Y^{\prime},Z) of the pair (X,Y) satisfying the inequality d_{H}(X^{\prime},Y^{\prime})\leq r is called the Gromov–Hausdorff distance between the metric spaces X and Y . It is well-known that the function d_{GH} is a generalized pseudometric on the proper class of all metric spaces considered up to an isometry. This means that d_{GH} can take infinite values ??and also be zero on a pair of non-isometric metric spaces. However, on the family of compact metric spaces, considered up to isometry, d_{GH} is a metric. For specific calculations of the Gromov–Hausdorff distance, the concept of distortion of generalized mappings — binary relations — turns out to be useful. A multivalued surjective mapping R from a set X to a set Y is called a correspondence . The set of all correspondences between X and Y is denoted by {\cal R}(X,Y) . Thus, a correspondence is a binary relation between X and Y for which the natural projections onto X and Y are surjective. For metric spaces X and Y and a binary relation \sigma\in{\cal P}_{0}(X\times Y) the value \operatorname{dis}\sigma:=\sup\Bigl\{\bigl||xx^{\prime}|-|yy^{\prime}|\bigr|:(x,y),\,(x^{\prime},y^{\prime})\in\sigma\Bigr\} is called the distortion of the binary relation \sigma . The next result is well-known, see, for example, [ 4 ] . Theorem 2.1 . For any non-empty metric spaces X and Y the following equality holds : d_{GH}(X,Y)=\frac{1}{2}\inf\bigl\{\operatorname{dis}R:R\in{\cal R}(X,Y)\bigr\}. For a cardinal number n , let \Delta_{n} denote the metric space of cardinality n in which all nonzero distances are equal to 1 . Note that \Delta_{1} is a one-point metric space. For a metric space X and a positive real number \lambda , let \lambda X denote the metric space obtained from X by multiplying all distances by \lambda . If X is bounded and \lambda=0 , then let \lambda X=\Delta_{1} . Clearly, \lambda\Delta_{1}=\Delta_{1} for every \lambda\geq 0 . The spaces \lambda\Delta_{n} are