|
This article is cited in 1 scientific paper (total in 1 paper)
Isometric embeddings of bounded metric spaces in the Gromov-Hausdorff class
A. O. Ivanovabc, A. A. Tuzhilina a Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
b Bauman Moscow State Technical University, Moscow, Russia
c Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia
Abstract:
We show that any bounded metric space can be embedded isometrically in the Gromov-Hausdorff metric class $\operatorname{\mathcal{G\!H}}$. This is a consequence of the description of the local geometry of $\operatorname{\mathcal{G\!H}}$ in a sufficiently small neighbourhood of a generic metric space, which is of independent interest. We use the techniques of optimal correspondences and their distortions.
Bibliography: 22 titles.
Keywords:
Gromov-Hausdorff distance, class of all metric spaces, von Neumann-Bernays-Gödel axioms, isometric embedding of a bounded metric space, generic metric space.
Received: 04.02.2022
Introduction Comparing metric spaces is of undoubted interest both from the theoretical and practical points of view. A possible approach to this general problem is to use some distance function between metric spaces: the less ‘similar’ two metric spaces are, the greater the distance between them. In general, the choice of a distance function and a particular class of spaces depends on the specifics of the problem under consideration. At this moment, the Gromov-Hausdorff distance seems to be used most often for these purposes. The history of this distance goes back to Hausdorff. In 1914 he introduced a nonnegative symmetric function on pairs of subsets of a metric space $X$ that equals the infimum of the real numbers $r$ such that the first subset is contained in an $r$-neighbourhood of the second and vice versa, and studied its properties; see [1]. This function satisfies the triangle inequality and, furthermore, is a metric on the family of nonempty closed bounded subsets of $X$. Subsequently, Edwards [2] and, independently, Gromov [3] extended Hausdorff’s construction to arbitrary metric spaces by using isometric embeddings in all possible ambient spaces; see a formal definition below. The resulting function is now called the Gromov-Hausdorff distance. Note that this function is also symmetric and nonnegative, and satisfies the triangle inequality. Moreover, it always vanishes at pairs of isometric spaces, so that such spaces are usually identified in this context. On the other hand the Gromov-Hausdorff distance can be infinite and can vanish for nonisometric spaces. Nevertheless, when restricted to the family $\mathcal{M}$ of isometry classes of compact metric spaces, the Gromov-Hausdorff distance satisfies all the axioms of a metric. The corresponding metric space $\mathcal{M}$ is called the Gromov-Hausdorff space. Its geometry turns out to be very complicated and is still under extensive investigation. It is well known that $\mathcal{M}$ is path-connected, Polish (that is, complete and separable), geodesic (see [4]) and not boundedly compact, and has only trivial symmetry (see [5]). For a detailed introduction to the geometry of the Gromov-Hausdorff distance see [6], Ch. 7, and [7]. The case of arbitrary metric spaces is also of great interest. To investigate it, many authors use modifications of the Gromov-Hausdorff distance. For example, pointed spaces can be included into consideration (under the assumption that the distinguished points coincide under isometric embeddings in ambient spaces); see [8] and [9]. In this paper we continue to investigate the properties of the classical Gromov-Hausdorff distance on the metric classes $\operatorname{\mathcal{G\!H}}$ and $\mathcal{B}$ that consist of representatives of isometry classes of all metric spaces and all bounded metric spaces, respectively. Here the term ‘class’ is used in the sense of von Neumann-Bernays-Gödel set theory (NGB). It is possible to define the Gromov-Hausdorff distance on the proper class $\operatorname{\mathcal{G\!H}}$ and consider an analogue of a metric topology by using the so-called filtration by sets [10]; see below. In [10], continuous curves in $\operatorname{\mathcal{G\!H}}$ were also defined and the Gromov-Hausdorff distance was shown to be an intrinsic extended pseudometric on $\operatorname{\mathcal{G\!H}}$ and $\mathcal{B}$, that is, the distance between two points is equal to the infimum of the lengths of curves connecting them. In [11] and [12] the geometry of path-connected components of $\operatorname{\mathcal{G\!H}}$ was studied ($\mathcal{B}$ is one of them) and it was proved that spheres in $\operatorname{\mathcal{G\!H}}$, $\mathcal{B}$ and, in some partial cases in $\mathcal{M}$ are path-connected. In [12] the concept of a generic space was also introduced and some properties were described; see below. Here we study the geometry of a sufficiently small neighbourhood of a generic space. It is shown that such a neighbourhood is isometric to a ball in the metric space $\mathbb{R}^\mathcal{N}$ endowed with the metric equal to the supremum of the differences of coordinates (here $\mathcal{N}$ is a suitable cardinal number); see Theorems 1 and 2. These results enable us to construct an isometric embedding of an arbitrary bounded space in the Gromov-Hausdorff class; see Theorem 3. Note that the question whether an unbounded space can be embedded in the Gromov-Hausdorff class remains open.
§ 1. Basic definitions and preliminary results Let $X$ be a set. We denote the cardinality of $X$ by $\#X$ and the set of its nonempty subsets by $\mathcal{P}_0(X)$. A symmetric map $d\colon X\times X\to[0,\infty]$ vanishing at each pair of identical elements is called a distance functions on $X$. If $d$ satisfies the triangle inequality, then $d$ is referred to as an extended pseudometric. If, in addition $d(x,y)>0$ for all $x\ne y$, then we say that $d$ is an extended metric. If $d(x,y)<\infty$ for all $x,y\in X$, then such a distance function is called a metric, and sometimes a finite metric to highlight the difference from an extended metric. A set $X$ with an (extended) (pseudo)metric is called an (extended) (pseudo)metric space. We also need the following simple properties of a metric. Proposition 1. The following assertions hold. (1) A nontrivial nonnegative linear combination of two metrics on an arbitrary set is a metric. (2) A positive linear combination of a metric and a pseudometric on an arbitrary set is a metric. If $X$ is a set with some distance function, then, as a rule, we denote the distance between points $x$ and $y$ by $|xy|$. In the case when it is necessary to clarify that the distance between $x$ and $y$ is considered exactly in $X$ we write $|xy|_X$. Now, if $\gamma\colon [a,b]\to X$ is a continuous curve in $X$, then the length $|\gamma|$ is defined as the supremum of the ‘lengths of inscribed polygonal paths’, that is, the quantities $\sum_i|\gamma(t_i)\gamma(t_{i+1})|$, where the supremum is taken over all possible finite partitions $a=t_1<\dots<t_k=b$ of $[a,b]$. A distance function on $X$ is called intrinsic if the distance between arbitrary points $x$ and $y$ equals the infimum of the lengths of curves connecting them. A curve $\gamma$ whose length differs from $|xy|$ by $\varepsilon$ at most is said to be $\varepsilon$-shortest. If for every points $x$ and $y$ of $X$ there is a curve whose length equals the infimum of the lengths of curves connecting these points and equals $|xy|$, then the distance is called strictly intrinsic and $X$ is referred to as a geodesic space. Let $X$ be a metric space. For $A,B\in\mathcal{P}_0(X)$ and $x\in X$ set
$$
\begin{equation*}
|xA|=|Ax|=\inf\bigl\{|xa|\colon a\in A\bigr\}, \qquad |AB|=\inf\bigl\{|ab|\colon a\in A,\,b\in B\bigr\}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
d_H(A,B)=\max\Bigl\{\sup_{a\in A}|aB|, \,\sup_{b\in B}|Ab|\Bigr\}=\max\Bigl\{\sup_{a\in A}\inf_{b\in B}|ab|,\,\sup_{b\in B}\inf_{a\in A}|ba|\Bigr\}.
\end{equation*}
\notag
$$
The function $d_H\colon \mathcal{P}_0(X)\times\mathcal{P}_0(X)\to[0,\infty]$ is called the Hausdorff distance. It is well known that $d_H$ is a metric on a subfamily $\mathcal{H}(X)\subset\mathcal{P}_0(X)$ of all the nonempty closed bounded subsets of $X$; see, for example, [6] or [7]. Let $X$ and $Y$ be metric spaces. A triple $(X',Y',Z)$ consisting of a metric space $Z$ and two subsets $X'$ and $Y'$ of $Z$ that are isometric to $X$ and $Y$, respectively, is called a realization of the pair $(X,Y)$. The Gromov-Hausdorff distance $d_{GH}(X,Y)$ between $X$ and $Y$ is defined as the infimum of the numbers $r$ such that there exists a realization $(X',Y',Z)$ of $(X,Y)$ with $d_H(X',Y')\leqslant r$. Note that the Gromov-Hausdorff distance can take finite and infinite values alike and satisfies the triangle inequality; see [6] or [7]. Also, this distance vanishes at every pair of isometric spaces. So the triangle inequality implies that the Gromov-Hausdorff distance is independent of the choice of representatives in classes of isometry. There are examples of nonisometric metric spaces with zero Gromov-Hausdorff distance: see, for example, [13]. Since every nonempty set can be endowed with a metric (for example, we can set all nonzero distances to be equal to $1$), the representatives of isometry classes form a proper class, which, endowed with the Gromov-Hausdorff distance, is denoted by $\operatorname{\mathcal{G\!H}}$. Here we use the concept of class in the sense of von Neumann-Bernays-Gödel set theory (NBG). Recall that all objects (analogues of ordinary sets) in NBG are referred to as classes. There are two types of classes: sets, that is, classes that are elements of other classes, and proper classes, all the remaining classes. The class of all sets is an example of a proper class. Many standard operations can be defined for classes, for example, taking the intersection or complement (for each class there is a class consisting of just those sets that are not included in it), Cartesian products, maps, and so on. The concepts of distance function, (extended) pseudometric and (extended) metric can be introduced for any class, be it a set or a proper class, because products and maps are defined for all classes. However, other notions, such as topology, cannot always be directly transferred to the case of proper classes. The following construction was introduced in [10]. For a class $\mathcal{C}$ consider a ‘filtration’ by the subclasses $\mathcal{C}_n$ each of which consists of all elements of cardinality at most $n$ of $\mathcal{C}$, for some cardinal number $n$. Recall that cardinality is well defined for elements of a class because every element is a set. A class $\mathcal{C}$ such that all the $\mathcal{C}_n$ are sets is said to be set filtered. Evidently, if $\mathcal{C}$ is a set, then it is set filtered. Let $\mathcal{C}$ be a set-filtered class. We say that this class has some property if this property holds for each $\mathcal{C}_n$. Now we give some examples. $\bullet $ A distance function on $\mathcal{C}$ induces an ‘ordinary’ distance function on each $\mathcal{C}_n$. Thus all the objects of metric geometry (for example, open balls) can be defined in each $\mathcal{C}_n$ (see above) and they are sets. This enables us to define a metric topology $\tau_n$ on $\mathcal{C}_n$ with the balls as a base. It is clear that if $n\leqslant m$, then $\mathcal{C}_n\subset\mathcal{C}_m$ and the topology $\tau_n$ on $\mathcal{C}_n$ is induced by $\tau_m$. $\bullet $ Also, a topology on a class $\mathcal{C}$ is defined if there is a topology $\tau_n$ on each $\mathcal{C}_n$ and the consistency condition holds: if $n\leqslant m$, then $\tau_n$ is a topology on $\mathcal{C}_n$ induced by $\tau_m$. We say that a class with a topology is a topological class. $\bullet $ If there is a topology on a class $\mathcal{C}$, then we can define a continuous map from a topological space $Z$ to $\mathcal{C}$. Note that the NBG axioms imply that for every map $f\colon Z\to\mathcal{C}$ the image $f(Z)$ is a set, all elements of $f(Z)$ are also sets and the union $\bigcup f(Z)$ is a set of cardinality, say, $n$. Therefore, every element of $f(Z)$ is of cardinality at most $n$ and so $f(Z)\subset\mathcal{C}_n$. We say that $f$ is continuous if $f$ is continuous as a map from $Z$ to $\mathcal{C}_n$. It follows from the consistency condition that $f$ is a continuous map from $Z$ to $\mathcal{C}_m$ for every $m\geqslant n$ and the map $f|_{\mathcal{C}_k}$ is continuous1[x]1When treated as a map from $Z$ to $\mathcal{C}_k$, $f$ is denoted by $f|_{\mathcal{C}_k}$. for every $k\leqslant n$ such that $f(Z)\subset\mathcal{C}_k$. $\bullet $ The above constructions enable us to define continuous curves in a topological class $\mathcal{C}$. $\bullet $ Let the class $\mathcal{C}$ be endowed with a distance function and the corresponding topology. The distance function is said to be intrinsic if it satisfies the triangle inequality and for any two elements of $\mathcal{C}$ lying at a finite distance this distance is the infimum of the lengths of curves connecting these elements. $\bullet $ Let $\{X_i\}$ be a sequence of elements of a topological class $\mathcal{C}$. Since $\{X_i\}_{i=1}^\infty$ is the image of the map $\mathbb{N}\to\mathcal{C}$, $i\mapsto X_i$, and $\mathbb{N}$ is a sequence, by the above argument $\{X_i\}$ is contained in some $\mathcal{C}_m$. Thus we can speak of the convergence of a sequence in a topological class. It is convergent if it is convergent in some and therefore every topology $\tau_m$ such that $\{X_i\}\subset\mathcal{C}_m$. Our main examples of topological classes are $\operatorname{\mathcal{G\!H}}$ and the class $\mathcal{B}$ of representatives of isometry classes of all bounded metric spaces. Note that $\operatorname{\mathcal{G\!H}}_n$ and $\mathcal{B}_n$ are sets for each cardinal number $n$. The set of all compact metric spaces, which is called the Gromov-Hausdorff space and often denoted by $\mathcal{M}$, is the best studied subset of $\operatorname{\mathcal{G\!H}}$. It is well known that the Gromov-Hausdorff distance is an intrinsic metric on $\mathcal{M}$ and the metric space $\mathcal{M}$ is Polish and geodesic (see [6], [7] and [4]). It was shown in [10] that the Gromov-Hausdorff distance is intrinsic on $\operatorname{\mathcal{G\!H}}$ and also on $\mathcal{B}$. As a rule, calculating the Gromov-Hausdorff distance between particular metric spaces is quite a complicated task and, as of today, this distance has only been found for a few pairs of spaces; see, for example, [14]. The most efficient approach to specific calculations is based on the following equivalent definition of the Gromov-Hausdorff distance; for details see [6] or [7]. Recall that a relation over two sets $X$ and $Y$ is a subset of the product $X\times Y$. Thus $\mathcal{P}_0(X\times Y)$ is the set of all nonempty relations over $X$ and $Y$. Definition 1. For $X,Y\in\operatorname{\mathcal{G\!H}}$ and $\sigma\in\mathcal{P}_0(X\times Y)$,
$$
\begin{equation*}
\operatorname{dis}\sigma=\sup\Bigl\{\bigl||xx'|-|yy'|\bigr|\colon (x,y),\,(x',y')\in\sigma\Bigr\}
\end{equation*}
\notag
$$
is called the distortion $\operatorname{dis}\sigma$ of the relation $\sigma$. A relation $R\subset X\times Y$ over $X$ and $Y$ is called a correspondence if the canonical projections $\pi_X\colon (x,y)\mapsto x$ and $\pi_Y\colon (x,y)\mapsto y$ are surjective on $R$. Note that correspondences are exactly surjective multivalued maps. For a correspondence $R\subset X\times Y$ and $x\in X$ set $R(x)=\{y\in Y\colon (x,y)\in R\}$. We say that $R(x)$ is the image of $x$. We denote the set of all correspondence over $X$ and $Y$ by $\mathcal{R}(X,Y)$. The following result is well known. Assertion 1. Let $X,Y\in\operatorname{\mathcal{G\!H}}$. Then
$$
\begin{equation*}
d_{GH}(X,Y)=\frac12\inf\bigl\{\operatorname{dis} R\colon R\in\mathcal{R}(X,Y)\bigr\}.
\end{equation*}
\notag
$$
We need the following estimates, implied easily by Assertion 1. Denote a single-point metric space by $\Delta_1$. Assertion 2. Let $X,Y\in\operatorname{\mathcal{G\!H}}$. Then $\bullet$ $2d_{GH}(\Delta_1,X)=\operatorname{diam} X$; $\bullet$ $2d_{GH}(X,Y)\leqslant\max\{\operatorname{diam} X,\operatorname{diam} Y\}$; $\bullet$ if $X$ or $Y$ is of finite diameter, then $|\operatorname{diam} X-\operatorname{diam} Y|\leqslant2d_{GH}(X,Y)$. For topological spaces $X$ and $Y$ we endow $X\times Y$ with the standard product topology. Thus, it makes sense to speak of closed relations and closed correspondences. A correspondence $R\in\mathcal{R}(X,Y)$ is said to be optimal if $2d_{GH}(X,Y)=\operatorname{dis} R$. We denote the set of optimal correspondences between $X$ and $Y$ by $\mathcal{R}_{\mathrm{opt}}(X,Y)$. Assertion 3 (see [15] and [16]). For every $X,Y\in\mathcal{M}$ there exist a closed optimal correspondence and a realization $(X',Y',Z)$ of $(X,Y)$ at which the Gromov-Hausdorff distance between $X$ and $Y$ is attained. Assertion 4 (see [15] and [16]). For every $X,Y\in\mathcal{M}$ and every closed optimal correspondence $R\in\mathcal{R}(X,Y)$ consider the family $R_t$, $t\in[0,1]$, of compact metric spaces such that $R_0=X$, $R_1=Y$, and for $t\in(0,1)$ the space $R_t$ is the set $R$ with the metric
$$
\begin{equation*}
\bigl|(x,y),(x',y')\bigr|_t=(1-t)|xx'|+t|yy'|.
\end{equation*}
\notag
$$
Then $R_t$ is a shortest curve in $\mathcal{M}$ connecting $X$ and $Y$ and has length $d_{GH}(X,Y)$. Let $X$ be a metric space and $\lambda$ be a positive real number. Denote by $\lambda X$ the metric space obtained from $X$ by multiplying all distances by $\lambda$, that is, $|xy|_{\lambda X}=\lambda|xy|_X$ for all $x,y\in X$. If $X$ is bounded, then for $\lambda=0$ set $\lambda X=\Delta_1$. Assertion 5. If $X,Y\in\operatorname{\mathcal{G\!H}}$ and $\lambda>0$, then $d_{GH}(\lambda X,\lambda Y)=\lambda\,d_{GH}(X,Y)$. If ${X,Y\in\mathcal{B}}$, then equality also holds for $\lambda=0$. Assertion 6. If $X\in\mathcal{B}$ and $\lambda_1,\lambda_2>0$, then $2d_{GH}(\lambda_1 X,\lambda_2 X)=|\lambda_1-\lambda_2|\operatorname{diam} X$. Remark 1. When $\operatorname{diam} X=\infty$, Assertion 6 does not hold in general. For example, let $X=\mathbb{R}$. Then $\lambda\mathbb{R}$ is isometric to $\mathbb{R}$ for every $\lambda>0$ and so $d_{GH}(\lambda_1\mathbb{R}, \lambda_2\mathbb{R})=0$.
§ 2. Generic spaces Let $I$ be a set of (possibly infinite) cardinality $n\geqslant2$. Denote the family of two-element subsets of $I$ by $\mathcal{N}=I^{(2)}$. An element $\{i,j\}\in\mathcal{N}$ is denoted by $ij$ (or $ji$). Note that the cardinality $N$ of $\mathcal{N}$ is equal to $n$ if and only if $n$ equals $3$ or $n$ is infinite. Consider the vector space $\mathbb{R}^\mathcal{N}$ of real functions on $\mathcal{N}$. For $v\in\mathbb{R}^\mathcal{N}$ we denote the coordinates $v(ij)=v(ji)$ of $v$ by $v_{ij}=v_{ji}$. We say that $v\in\mathbb{R}^\mathcal{N}$ is a metric vector or simply a metric if $v_{ij}>0$ when $ij\in\mathcal{N}$ (positive definite) and $v_{ij}+v_{jk}\geqslant v_{jk}$ for $ij,jk,ik\in\mathcal{N}$ (the triangle inequality). The subset $C_n\subset\mathbb{R}^\mathcal{N}$ consisting of all metrics is called the metric cone. This name is justified by the fact that $C_n$ is invariant under multiplication by positive numbers. Let $X$ be a metric space of cardinality $n$ and $\eta\colon I\to X$ be a bijection. We denote the set of such bijections by $B(X)$ and refer to them as enumerations of $X$. Put $\rho_X^\eta(ij)=|\eta(i)\eta(j)|$. Then by the properties of a metric we have $\rho_X^\eta\in C_n$. We say that $\rho_X^\eta$ is the vector of distances of $X$ corresponding to the enumeration $\eta$. On the other hand let $v\in C_n$, let $Z$ be a set of the same cardinality as $I$ and $\eta\colon I\to Z$ be an enumeration of $Z$. Then the function on $Z\times Z$ that vanishes on the diagonal $\{(z,z)\}_{z\in Z}$ and maps each pair $(z,z')$ with $z\ne z'$ to $v_{\eta^{-1}(z)\eta^{-1}(z')}$ is a metric such that $v=\rho_Z^\eta$. Thus, the cone $C_n$ consists exactly of the vectors of distances of all possible metric spaces of cardinality $n$ obtained from all possible enumerations of these spaces. Remark 2. For finite $n$ take $\{1,\dots,n\}$ as $I$ and map every subset $\{i,j\}\subset I$, $i\ne j$, to the basis vector $e_{ij}=e_{ji}$ in $\mathbb{R}^N$. Then we obtain a natural identification of the spaces $\mathbb{R}^N$ and $\mathbb{R}^\mathcal{N}$. We endow $\mathbb{R}^\mathcal{N}$ with a distance by putting $|vw|=\frac12\sup_{ij\in\mathcal{N}}|v_{ij}-w_{ij}|$ for every $v,w\in\mathbb{R}^\mathcal{N}$. This distance is an extended metric. The vector $v\in\mathbb{R}^\mathcal{N}$ is said to be bounded if there exists $c>0$ such that $|v_{ij}|<c$ for all $ij\in\mathcal{N}$; otherwise it is said to be unbounded. It is easy to see that the property of vectors in $\mathbb{R}^\mathcal{N}$ to lie at a finite distance, that is, to have a bounded difference, is an equivalence relation. Equivalence classes are called clouds. The cloud containing the origin $0\in\mathbb{R}^\mathcal{N}$ consists of all bounded vectors and is denoted by $\mathbb{R}^\mathcal{N}_\infty$. It is clear that $\mathbb{R}^\mathcal{N}_\infty$ is a vector subspace of $\mathbb{R}^\mathcal{N}$ and the distance to $0$ on it is equal to half the $\sup$-norm2[x]2This $\sup$-norm can be extended to the whole of $\mathbb{R}^\mathcal{N}$. The resulting function can take the value $\infty$. Such functions are called generalized norms. However, there is a difficulty with the formulation of the axiom of positive homogeneity, $\|\lambda v\|=|\lambda|\,\|v\|$, because an uncertainty arises when $\lambda=0$ and $\|v\|=\infty$. One possible approach is to set $0\cdot\infty=0$ as in measure theory. However, then the map $(\lambda,v)\to\|\lambda v\|$ is discontinuous at $(0,v)$ for $\|v\|=\infty$. Another approach is that the axiom of homogeneity is assumed to hold only for $\lambda\ne0$. $\|v\|_\infty=\sup_{ij\in\mathcal{N}}|v_{ij}|$. Now we describe what other clouds look like. Proposition 2. Every cloud other than $\mathbb{R}^\mathcal{N}_\infty$ is an affine subspace of the form ${v+\mathbb{R}^\mathcal{N}_\infty}$, where $v$ is an unbounded vector. If $v$ is an unbounded vector, then for every $\lambda\ne 1$ the vectors $v$ and $\lambda v$ lie in different clouds. Proof. To prove the first assertion note that the condition
$$
\begin{equation*}
2|vw|=\sup_{ij\in\mathcal{N}}|v_{ij}-w_{ij}|<\infty
\end{equation*}
\notag
$$
is equivalent to the boundedness of the vector with coordinates $v_{ij}-w_{ij}$, which means that $v-w\in\mathbb{R}^\mathcal{N}_\infty$.
Next we prove the second assertion. Let $v\in\mathbb{R}^\mathcal{N}$ be an unbounded vector. Then there exists a sequence $v_{i_kj_k}$ tending to infinity. Hence
$$
\begin{equation*}
2|(\lambda v)v|\geqslant|\lambda-1|\cdot|v_{i_kj_k}|\to\infty,
\end{equation*}
\notag
$$
as required.
The proof is complete. Let $\operatorname{\mathcal{G\!H}}_{[n]}\subset\operatorname{\mathcal{G\!H}}$ consist of all metric spaces of cardinality $n$. As noted above, $\operatorname{\mathcal{G\!H}}_n$ is a set, hence so is also $\operatorname{\mathcal{G\!H}}_{[n]}\subset\operatorname{\mathcal{G\!H}}_n$. As for finite spaces, for $C_n\subset\mathbb{R}^\mathcal{N}$ we define a map $\pi\colon C_n\to\operatorname{\mathcal{G\!H}}_{[n]}$ by putting $\pi(v)$ equal to the unique representative of the isometry class of the metric space $I$ of cardinality $n$ in $\operatorname{\mathcal{G\!H}}_{[n]}$ such that $|ij|=v_{ij}$ for $i,j\in I$, $i\ne j$, and all the distances $|ii|$ are zero. We say that $\pi$ is the canonical projection. Proposition 3. $\pi\colon C_n\to\operatorname{\mathcal{G\!H}}_{[n]}$ is a $1$-Lipschitz map, that is,
$$
\begin{equation*}
d_{GH}\bigl(\pi(v),\pi(w)\bigr)\leqslant|vw|.
\end{equation*}
\notag
$$
Proof. If $v,w\in\mathbb{R}^\mathcal{N}$ lie in the same cloud, then we set $X=\pi(v)$ and $Y=\pi(w)$. Let $\eta\in B(X)$ and $\mu\in B(Y)$ be enumerations such that $v=\rho_X^{\eta}$ and $w=\rho_Y^{\mu}$. Next we define a bijective correspondence $R\in\mathcal{R}(X,Y)$ by putting $R=\{(x_i,y_i)\}_{i=1}^n$, where $x_i=\eta(i)$ and $y_i=\mu(i)$. Then
$$
\begin{equation*}
2|vw|=\sup_{ij\in\mathcal{N}}|v_{ij}-w_{ij}|=\sup_{ij\in\mathcal{N}}\bigl||x_ix_j|-|y_iy_j|\bigr|=\operatorname{dis} R\geqslant2d_{GH}(X,Y),
\end{equation*}
\notag
$$
as required.
If $|vw|=\infty$, then the assertion also holds regardless of the value of $d_{GH}(\pi(v),\pi(w))$.
The proof is complete. Let $\mathcal{B}_{[n]}$ denote the set of all bounded spaces of cardinality $n$. Proposition 4. The equality $\pi(C_n\cap\mathbb{R}^\mathcal{N}_\infty)=\mathcal{B}_{[n]}$ holds. Moreover, $\pi(C_n\cap\mathcal{A})\cap\mathcal{B}_{[n]}=\varnothing $ for every cloud $\mathcal{A}\subset\mathbb{R}^\mathcal{N}$ other than $\mathbb{R}^\mathcal{N}_\infty$. Proof. A metric space $X$ is bounded if and only if the distances are bounded, which in turn is equivalent to the condition that the components of $\rho^\eta_X$ are bounded for every enumeration $\eta\in B(X)$. The proof is complete. Remark 3. Clouds other than $\mathbb{R}^\mathcal{N}_\infty$ can be mapped to a single cloud in $\operatorname{\mathcal{G\!H}}_{[n]}$. Indeed, let $X=\mathbb{N}$ be the set of positive integers endowed with the natural distance. Denote by $\nu$ the bijective map from $A=\{2^{n-1}\}_{n\in\mathbb{N}}$ to the set $B\subset\mathbb{N}$ of odd numbers given by $\nu(2^{n-1})=2n-1$. Let $\mu\colon \mathbb{N}\setminus A\to\mathbb{N}\setminus B$ be an arbitrary bijection. Denote by $\eta\colon \mathbb{N}\to\mathbb{N}$ the enumeration coinciding with $\nu$ on $A$ and with $\mu$ on $\mathbb{N}\setminus A$. Let $\mathrm{id}\colon \mathbb{N}\to\mathbb{N}$ be the tautological enumeration. Set $v=\rho_\mathbb{N}^{\mathrm{id}}$ and $w=\rho_\mathbb{N}^\eta$. Then
$$
\begin{equation*}
|vw|\geqslant\sup_{n\in\mathbb{N}}\bigl|((2n+1)-(2n-1))-(2^n-2^{n-1})\bigr|=\infty.
\end{equation*}
\notag
$$
Hence $v$ and $w$ lie in different clouds of the corresponding space $\mathbb{R}^\mathcal{N}$ but are mapped to the same cloud in $\operatorname{\mathcal{G\!H}}_{[\aleph_0]}$, where $\aleph_0$ is the countable cardinal number. The following natural question arises: is it true that if the Gromov-Hausdorff distance between two metric spaces $X$ and $Y$ of equal cardinality is finite, then there exists a bijection of finite distortion between them? In other words, is it true that for some enumerations $\eta\in B(X)$ and $\mu\in B(Y)$ the distance between $\rho^\eta_X$ and $\rho^\mu_Y$ is finite? The following example shows that this is not the case. Example 1. Let $X=\{2^n\}_{n\in\mathbb{N}}\subset\mathbb{R}$ and $Y=X\cup\{2^n+1\}_{n\in\mathbb{N}}\subset\mathbb{R}$. Consider the correspondence $R\in\mathcal{R}(X,Y)$ of the form $\{(2^n,2^n),(2^n,2^n+1)\}_{n\in\mathbb{N}}$. Then $\operatorname{dis} R=1$ and so $d_{GH}(X,Y)<\infty$. Let $R'\in\mathcal{R}(X,Y)$ be a bijection. Then for every $k\in\mathbb{N}$ there exist $(2^m,2^n),(2^p,2^n+1)\in R'$ such that $m,n,p>k$. Since $R'$ is bijective, it follows that $p\ne m$ and thus $\operatorname{dis} R'\geqslant|2^p-2^m|-1\geqslant2^{\min(p,m)}-1\to\infty$ as $k\to\infty$. So $\operatorname{dis} R'=\infty$ for every bijection $R'$. To transfer the concepts of so-called boundary and interior spaces (cf. [17]), as well as the concept of a generic space, to the case of infinite spaces, we need to introduce a number of numerical characteristics of metric spaces. Let $X$ be a metric space with $\#X\geqslant3$. Denote the set of all bijections from $X$ to itself by $S(X)$ and the identity bijection by $\operatorname{id}\in S(X)$. Set
$$
\begin{equation*}
\begin{gathered} \, s(X)=\inf\bigl\{|xx'|\colon x\ne x',\ x,x'\in X\bigr\}, \\ t(X)=\inf\bigl\{|xx'|+|x'x''|-|xx''|\colon x\ne x'\ne x''\ne x,x,x',x''\in X\bigr\} \end{gathered}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
e(X)=\inf\bigl\{\operatorname{dis} f\colon f\in S(X),\ f\ne\operatorname{id}\bigr\}.
\end{equation*}
\notag
$$
A metric space $M\in\operatorname{\mathcal{G\!H}}$, $\#M\geqslant3$, is said to be generic if all the three of its characteristics $s(M)$, $t(M)$ and $e(M)$ are strictly positive. Remark 4. When the first characteristic $s(M)$ is strictly positive, the distances between different points in $M$ are bounded away from zero, in particular, $M$ is discrete. A space $M$ such that $s(M)>0$ is said to be totally discrete. The second characteristic $t(M)$ shows how far the triangles in $M$ are from being degenerate. A space $M$ such that $t(M)>0$ is said to be totally nondegenerate. Finally, the third characteristic $e(M)$ is responsible for the extent of asymmetry of $M$. A space $M$ such that $e(M)>0$ is said to be totally asymmetric. Thus, a generic space is a totally discrete, totally nondegenerate and totally asymmetric metric space. Remark 5. Finite generic metric spaces were considered in [17] and also by Filin in [18]. The first steps in the investigation of generic spaces of arbitrary cardinality were made by Filin in his master thesis (he proved several assertions in Theorem 1 and an analogue of Proposition 5). It is easy to construct an example of a generic metric space $M$ of finite cardinality $n\geqslant3$. Indeed, starting with a simplex $\Delta_n$, we can add distinct real numbers of modulus less than $1/3$ to all distances. Then we have $s(M)>2/3$, $t(M)>0$ and $e(M)>0$, so that $M$ is generic. Now we show how we can obtain generic metric spaces of arbitrary infinite cardinality. This construction is due to Shramov. Construction 1. Let $X$ be an infinite set. Recall that every set can be well ordered, that is, there exists a linear order such that each subset contains a minimal element. It is easy to check that no bijection other than the identity map preserves this total order; see, for example, [19], Ch. 2. Fix a well-order $<$ on $X$. Let $G_o$ be the oriented graph such that $X$ is its vertex set and all pairs of the form $(x,y)$, where $x<y$, are edges. It follows from the above that the identity map is the only automorphism of the graph $G_o$. Now we construct another directed graph $H_o$ by replacing each edge $e=(x,y)$ of $G_o$ with three vertices $u_e$, $v_e$, $w_e$ and four edges $(x,u_e)$, $(u_e,v_e)$, $(v_e,y)$, $(v_e,w_e)$ (Fig. 1). Let $H$ denote the unoriented graph corresponding to $H_o$. We claim that $H$ has no nontrivial automorphisms. Indeed, $X$ coincides with the set of vertices of infinite degree in $H$, and so every automorphism $\nu$ of $H$ preserves $X$. Let $e=(x,y)$ be an edge of $G_o$. We show that $(\nu(x),\nu(y))$ is also an edge of $G_0$. Assume the opposite, that is, let the pair $f=(\nu(y),\nu(x))$ be an edge of the graph $G_0$. Note that $\nu$ takes the path $xu_ev_ey$ in $H$ to the path $\nu(x)\nu(u_e)\nu(v_e)\nu(y)$. Since $\nu(y)u_fv_f\nu(x)$ is a unique path of length $3$ in $H$ connecting $\nu(x)$ and $\nu(y)$, we conclude that $\nu(v_e)=u_f$ and $\nu(u_e)=v_f$. Hence we obtain a contradiction because $v_e$ is a vertex of degree $3$ in $H$ but $u_f$ is of degree $2$. Therefore, $(\nu(x),\nu(y))$ is an edge of $G_o$. Thus, the restriction of each automorphism $\nu$ of $H$ to $X$ preserves the order, and then by the above the restriction of $\nu$ to $X$ is the identity map. Hence the vertices of paths of the form $xu_ev_ey$ are also fixed and so is $w_e$. Let $V$ be the set of vertices of $H$. Note that when $X$ is infinite, the cardinalities of $V$ and $X$ coincide. We define a metric on $V$ by setting the distance between distinct nonadjacent vertices equal to $1$ and that between adjacent vertices equal to $1+\varepsilon$, where $0<\varepsilon<1$. It is clear that $s(V)=1$ and $t(V)=1-\varepsilon>0$. Note that the distortion of each bijection of $V$ onto itself that is not an automorphism of $H$ is equal to $\varepsilon$. Therefore, since $H$ has no nontrivial automorphisms, we conclude that $e(V)=\varepsilon$. Thus, $V$ is a generic space. In the following theorem we list some properties of totally discrete spaces. Theorem 1. Let $M\in\operatorname{\mathcal{G\!H}}$ be a totally discrete metric space, that is, $\#M\geqslant3$ and $s(M)>0$, and let $\varepsilon\in(0,s(M)/2]$. Then for every space $X\in\operatorname{\mathcal{G\!H}}$ such that $r:=d_{GH}(M,X)<\varepsilon$ the following assertions hold. (1) There is a correspondence $R\in\mathcal{R}(M,X)$ such that $\operatorname{dis} R<2\varepsilon$. (2) Let $R$ be such a correspondence. Then $R(i)\cap R(j)=\varnothing $ for $i,j\in M$, $i\ne j$, that is, the family $D_R=\{X_i:=R(i)\}_{i\in M}$ is a partition of $X$. (3) If $i,j\in M$ ($i\ne j$), $x_i\in X_i$ and $x_j\in X_j$, then $\bigl||x_ix_j|-|ij|\bigr|<2\varepsilon$. (4) For every $i\in M$ the inequality $\operatorname{diam} X_i<2\varepsilon$ holds. (5) If $\varepsilon\leqslant s(M)/4$, then $D_R$ is unique, that is, if $\operatorname{dis} R'<2\varepsilon$ for $R'\in\mathcal{R}(M,X)$, then $D_{R'}=D_R$. (6) Suppose, in addition, that $M$ is asymmetric, that is, $e(M)\!>\!0$. Let ${\varepsilon\!\leqslant\! s(M)/4}$ and $\varepsilon<e(M)/4$. Then the correspondence $R\in\mathcal{R}(M,X)$ with $\operatorname{dis} R<2\varepsilon$ is unique, so that $R$ is an optimal correspondence. Proof. (1) Since
$$
\begin{equation*}
d_{GH}(M,X)=\frac12\inf\bigl\{\operatorname{dis} R\colon R\in\mathcal{R}(M,X)\bigr\}<\varepsilon,
\end{equation*}
\notag
$$
there exists a correspondence $R\in\mathcal{R}(M,X)$ such that $\operatorname{dis} R<2\varepsilon$.
(2) If there is $x\in X$ such that $x\in R(i)\cap R(j)$, $i\ne j$, then $\#R^{-1}(x)>1$. Then
$$
\begin{equation*}
\operatorname{dis} R\geqslant\operatorname{diam} R^{-1}(x)\geqslant s(M)\geqslant2\varepsilon
\end{equation*}
\notag
$$
and we obtain a contradiction. Therefore, distinct sets $X_i:=R(i)$ do not intersect and form a partition $\{X_i\}_{i\in M}$ of $X$.
(3) Since $\operatorname{dis} R<2\varepsilon$, for $i,j\in M$, $i\ne j$, and $x_i\in R(i)$, $x_j\in R(j)$ we have
$$
\begin{equation*}
\bigl||x_ix_j|-|ij|\bigr|\leqslant\operatorname{dis} R<2\varepsilon.
\end{equation*}
\notag
$$
(4) Since $\operatorname{dis} R\,{<}\,2\varepsilon$, we have $\operatorname{diam} X_i\,{\leqslant}\operatorname{dis} R\,{<}\,2\varepsilon$ for every $i \in M$.
(5) Let $\varepsilon\leqslant s(M)/4$ and $R'\in\mathcal{R}(M,X)$ be another correspondence such that $\operatorname{dis} R'<2\varepsilon$. Then $\{X'_i:=R'(i)\}_{i\in M}$ is a partition of $X$ with the above properties. If $D_R\ne D_{R'}$, then either there exists $X'_i$ intersecting two distinct sets $X_j$ and $X_k$ or there exists $X_i$ intersecting two distinct sets $X'_j$ and $X'_k$. Indeed, if there is no such $X'_i$, then $X'_i$ is contained in some $X_j$ and so $\{X'_p\}$ is a subpartition of $\{X_q\}$. Since these partitions do not coincide, there exists $X_i$ containing distinct sets $X'_j$ and $X'_k$.
Thus, without loss of generality we can assume that $X'_i$ intersects two distinct sets $X_j$ and $X_k$. Fix two points $x_j\in X_j\cap X'_i$ and $x_k\in X_k\cap X'_i$. Then
$$
\begin{equation*}
2\varepsilon>\operatorname{diam} X'_i\geqslant|x_jx_k|>|jk|-2\varepsilon\geqslant s(M)-2\varepsilon,
\end{equation*}
\notag
$$
and therefore $\varepsilon>s(M)/4$. This is a contradiction.
(6) Let $R'\in\mathcal{R}(M,X)$ satisfy $\operatorname{dis} R'<2\varepsilon$. Then, as shown above, $D_R=D_{R'}$. It remains to check that $X_i=X'_i$ for every $i\in M$. Assume the opposite, that is, suppose there is a nontrivial bijection $\sigma\colon M\to M$ such that $X_i=X'_{\sigma(i)}$. By assumption $\operatorname{dis}\sigma\geqslant e(M)>4\varepsilon$. This means that there are $i,j\in M$ such that
$$
\begin{equation*}
\bigl||ij|-|\sigma(i)\sigma(j)|\bigr|>4\varepsilon.
\end{equation*}
\notag
$$
Set $p=\sigma(i)$, $q=\sigma(j)$ and fix arbitrary $x_i\in X_i=X'_p$ and $x_j\in X_j=X'_q$. Then
$$
\begin{equation*}
4\varepsilon\,{<}\,\bigl||pq|-|ij|\bigr|\,{=}\,\bigl||pq|-|x_ix_j|+|x_ix_j|-|ij|\bigr|\,{\leqslant}\, \bigl||pq|-|x_ix_j|\bigr|+\bigl||x_ix_j|-|ij|\bigr|\,{<}\,2\varepsilon+2\varepsilon
\end{equation*}
\notag
$$
and we obtain a contradiction. Thus, a correspondence $R$ with distortion close enough to $2d_{GH}(M,X)$ is uniquely defined. Hence $R$ is optimal.
The proof is complete. Definition 2. The family $\{X_i\}$ in Theorem 1 is called a canonical partition of $X$ with respect to $M$. Proposition 5. Let $M$ be a totally discrete metric space, that is, $\#M\geqslant3$ and $s(M)>0$, and let $\varepsilon\in(0,s(M)/8]$. Then for any ${X,Y\in\operatorname{\mathcal{G\!H}}}$ satisfying ${d_{GH}(M,X)\,{<}\,\varepsilon}$ and $d_{GH}(M,Y)\,{<}\, \varepsilon$ the corresponding canonical partitions $\{X_i\}_{i\in M}$ and $\{Y_i\}_{i\in M}$ with respect to $M$ are uniquely defined, there exists a correspondence $R\in\mathcal{R}(X,Y)$ satisfying $\operatorname{dis} R<4\varepsilon$, and for each such correspondence there is a bijection $\sigma\colon M\to M$ such that $R$ has the form $R=\bigsqcup_{i\in M}R_i$ for some ${R_i\in\mathcal{R}(X_i,Y_{\sigma(i)})}$. Proof. It follows from the triangle inequality that $d_{GH}(X,Y)\leqslant d_{GH}(X,M)+d_{GH}(M,Y)<2\varepsilon$. Hence there is $R$ satisfying the desired inequality.
Fix arbitrary points $x,x'\in X_i$ and $y\in R(x)$, $y'\in R(x')$. We claim that there exists $Y_j$ containing $y$ and $y'$. Assume the opposite, that is, let $y\in Y_j$ and $y'\in Y_k$ for some $j\ne k$. Then by Theorem 1,
$$
\begin{equation*}
|xx'|\leqslant\operatorname{diam} X_i<2\varepsilon\quad\text{and}\quad |yy'|>|jk|-2\varepsilon\geqslant s(M)-2\varepsilon\geqslant6\varepsilon
\end{equation*}
\notag
$$
and so $\operatorname{dis} R\geqslant\bigl||xx'|-|yy'|\bigr|>4\varepsilon$, which is a contradiction.
Swapping $X$ and $Y$ we conclude that for any $(x,y),(x',y')\in R$ the points $x$ and $x'$ lie in the same element of $\{X_i\}$ if and only if $y$ and $y'$ lie in the same element of $\{Y_i\}$, which completes the proof. Proposition 6. Let $M\in\operatorname{\mathcal{G\!H}}$ be a totally discrete and totally asymmetric space, that is, $\#M\geqslant3$, $s(M)>0$ and $e(M)>0$. Fix an arbitrary $\varepsilon\in(0,s(M)/8]$ such that $\varepsilon<e(M)/8$. Then for any $X,Y\in\operatorname{\mathcal{G\!H}}$ satisfying $d_{GH}(M,X)<\varepsilon$ and $d_{GH}(M,Y)< \varepsilon$ the corresponding canonical partitions $\{X_i\}_{i\in M}$ and $\{Y_i\}_{i\in M}$ with respect to $M$ are uniquely defined, and there is a correspondence $R\in \mathcal{R}(X,Y)$ satisfying $\operatorname{dis} R< 4\varepsilon$. All such $R$ have the form $R=\bigsqcup_{i\in M}R_i$ for some ${R_i\in\mathcal{R}(X_i,Y_i)}$. Proof. It follows from Proposition 5 that there exists a correspondence $R\in\mathcal{R}(X,Y)$ satisfying $\operatorname{dis} R<4\varepsilon$, and for each such correspondence there exist a bijection $\sigma\colon M\to M$ and correspondences $R_i\in\mathcal{R}(X_i,Y_{\sigma(i)})$ such that $R=\bigsqcup_{i\in M}R_i$. We must prove that $\sigma$ is the identity map.
Assume the opposite. Then $\operatorname{dis}\sigma\geqslant e(M)>8\varepsilon$ and therefore there exist $i,j\in M$ such that for $k=\sigma(i)$ and $l=\sigma(j)$ we have $\bigl||ij|-|kl|\bigr|>8\varepsilon$. By hypothesis $\bigl||y_ky_l|-|kl|\bigr|<2\varepsilon$, $\bigl||x_ix_j|-|ij|\bigr|<2\varepsilon$ and $\bigl||x_ix_j|-|y_ky_l|\bigr|\leqslant\operatorname{dis} R<4\varepsilon$ for all $x_i\in X_i$, $x_j\in X_j$, $y_k\in R(x_i)\subset Y_k$ and $y_l\in R(x_j)\subset Y_l$. So we have
$$
\begin{equation*}
\begin{aligned} \, \bigl||ij|-|kl|\bigr|\ &=\bigl||ij|-|x_ix_j|+|x_ix_j|-|y_ky_l|+|y_ky_l|-|kl|\bigr| \\ &\leqslant \bigl||ij|-|x_ix_j|\bigr|+\bigl||x_ix_j|-|y_ky_l|\bigr|+\bigl||y_ky_l|-|kl|\bigr|<8\varepsilon, \end{aligned}
\end{equation*}
\notag
$$
which is a contradiction. The proof is complete. Theorem 2. Let $n\geqslant3$ be a cardinal number, $I$ be a set of cardinality $n$ and $\mathcal{N}=I^{(2)}$ be the set of $2$-element subsets of $I$. Let $C_n\subset\mathbb{R}^\mathcal{N}$ be the metric cone and $\pi\colon{C_n\to\operatorname{\mathcal{G\!H}}_{[n]}}$ be the canonical projection. Assume that $\operatorname{\mathcal{G\!H}}_{[n]}$ contains a totally discrete and totally asymmetric space $M$, and let $w\in\pi^{-1}(M)$. Fix ${\varepsilon\in(0,s(M)/8]}$ such that ${\varepsilon<e(M)/8}$, and let $U_\varepsilon(w)\subset\mathbb{R}^\mathcal{N}$ be the corresponding open ball in $\mathbb{R}^\mathcal{N}$. Then the restriction of $\pi$ to $U_\varepsilon:=U_\varepsilon(w)\cap C_n$ is an isometry. Proof. Let $w=\rho^\eta_M$ for some enumeration $\eta\in B(M)$. For $i\in I$ set $m_i=\eta(i)$.
Fix arbitrary $a,b\in U_\varepsilon$, and let $X=\pi(a)$ and $Y=\pi(b)$. Since $\pi$ is a $1$-Lipschitz map by Proposition 3, we have $d_{GH}(X,M)\leqslant|aw|<\varepsilon$ and $d_{GH}(Y,M)\leqslant|bw|<\varepsilon$. So by Theorem 1 the corresponding canonical partitions $\{X_i\}_{m_i\in M}$ and $\{Y_i\}_{m_i\in M}$ of the spaces $X$ and $Y$ are uniquely defined. Let $R_X\in\mathcal{R}(M,X)$ and $R_Y\in\mathcal{R}(M,Y)$ be correspondences that satisfy $\operatorname{dis} R_X<2\varepsilon$ and $\operatorname{dis} R_Y<2\varepsilon$ and define these partitions. By Theorem 1 the correspondences $R_X$ and $R_Y$ are uniquely defined and optimal, that is, $2d_{GH}(M,X)=\operatorname{dis} R_X$ and $2d_{GH}(M,Y)=\operatorname{dis} R_Y$.
For $x\in\mathbb{R}^\mathcal{N}$ set $s(x)=\inf_{ij\in \mathcal{N}} x_{ij}$. Note that $s(X)=s(a)\geqslant s(w)-2\varepsilon=s(M)-2\varepsilon\geqslant6\varepsilon$ and similarly $s(Y)\geqslant6\varepsilon$. On the other hand Theorem 1 implies that $\operatorname{diam} X_i<2\varepsilon$ and $\operatorname{diam} Y_i<2\varepsilon$ for every $m_i\in M$. Therefore, all the $X_i$ and $Y_i$ are single-element sets, that is, $X_i=\{x_i\}$ and $Y_i=\{y_i\}$. Thus, $R_X=\{(m_i,x_i)\}_{i\in I}$ and $R_Y=\{(m_i,y_i)\}_{i\in I}$.
It follows from Proposition 6 that there exists a correspondence $R\in\mathcal{R}(X,Y)$ such that $\operatorname{dis} R<4\varepsilon$ and every such correspondence has the form $R=\bigsqcup_{m_i\in M}R_i$, where $R_i\in\mathcal{R}(X_i,Y_i)$. Since $X_i$ and $Y_i$ are single-element sets, $R$ is a bijection consisting of all pairs $(x_i,y_i)$. Thus $R$ is uniquely defined. Hence, if a correspondence in $\mathcal{R}(X,Y)$ has distortion less than $4\varepsilon$, then it coincides with $R$. Therefore, $R$ is an optimal correspondence, and so $2d_{GH}(X,Y)=\operatorname{dis} R$.
Note that $\eta_X\colon i\mapsto x_i$ and $\eta_Y\colon i\mapsto y_i$ are enumerations of $X$ and $Y$. Thus, we can define the vectors $\rho_X:=\rho^{\eta_X}_X$ and $\rho_Y:=\rho^{\eta_Y}_Y$ in $C_n$. We claim that $a=\rho_X$ and $b=\rho_Y$. Indeed, note first that $|aw|<\varepsilon$ and
$$
\begin{equation*}
|\rho_Xw|=\frac12\sup_{ij\in\mathcal{N}}\bigl||x_ix_j|-|m_im_j|\bigr|=\frac12\operatorname{dis} R_X=d_{GH}(M,X)<\varepsilon.
\end{equation*}
\notag
$$
If $\eta'_X$ is an enumeration of $X$ different from $\eta$ and if $\rho'_X:=\rho^{\eta'_X}_X$, then $|\rho_X\rho'_X|=\frac12\operatorname{dis}\sigma_X$, where $\sigma_X\colon X\to X$ is a nonidentity bijection corresponding to another enumeration, that is, $\sigma_X=\eta'_X\circ\eta^{-1}_X$. Let $\sigma_X(x_i)=x_{i'}$. Then we have a bijection $\sigma_M\colon M\to M$, $\sigma_M\colon m_i\mapsto m_{i'}$. By assumption $\operatorname{dis}\sigma_M\geqslant e(M)>8\varepsilon$. Then
$$
\begin{equation*}
\begin{aligned} \, |\rho'_Xw| &=\frac12\sup_{ij\in\mathcal{N}}\bigl||x_{i'}x_{j'}|-|m_im_j|\bigr| \,{=}\,\frac12\sup_{ij\in\mathcal{N}}\bigl||x_{i'}x_{j'}|\,{-}\,|m_{i'}m_{j'}|\,{+}\,|m_{i'}m_{j'}| \,{-}\,|m_im_j|\bigr| \\ &\geqslant \frac12\sup_{ij\in\mathcal{N}}\bigl||m_{i'}m_{j'}|-|m_im_j|\bigr| -\frac12\sup_{ij\in\mathcal{N}}\bigl||x_{i'}x_{j'}|-|m_{i'}m_{j'}|\bigr| \\ &=\frac12(\operatorname{dis}\sigma_M-\operatorname{dis} R_X)>\frac12(8\varepsilon-2\varepsilon)=3\varepsilon. \end{aligned}
\end{equation*}
\notag
$$
Hence each point distinct from $\rho_X$ in $\pi^{-1}(X)$ lies outside $U_\varepsilon$. The same holds for $Y$.
Thus, of all points in $\pi^{-1}(X)$ and $\pi^{-1}(Y)$, only $\rho_X$ and $\rho_Y$ lie in $U_\varepsilon$. Therefore, $a=\rho_X$ and $b=\rho_Y$. Finally, note that
$$
\begin{equation*}
|ab|=|\rho_X\rho_Y|=\frac12\sup_{ij\in\mathcal{N}}\bigl||x_ix_j|-|y_iy_j|\bigr|=\frac12\operatorname{dis} R=d_{GH}(X,Y),
\end{equation*}
\notag
$$
as required. The proof is complete. When $n$ is infinite, a space $Z\in\operatorname{\mathcal{G\!H}}_{[n]}$ that is very close to a totally discrete and totally asymmetric space $M$ need not be totally discrete (blowing up points to small subspaces of the same cardinality does not change the distance of $Z$ to $M$). Thus the image of the neighbourhood $U_\varepsilon(w)\cap C_n$ in Theorem 2 under a canonical projection does not coincide with $U_\varepsilon(M)\cap\operatorname{\mathcal{G\!H}}_{[n]}$. When $n$ is finite, each such space $Z\in\mathcal{M}_{[n]}$ contains exactly $n$ points and the distance $d_{GH}(M,Z)$ is attained at a bijection. In fact, this bijection transfers enumeration from $M$ to $Z$. Hence the corresponding $\rho_Z$ occurs in $U_\varepsilon(w)\cap C_n$. Thus, a canonical projection $\pi$ maps $U_\varepsilon(w)\cap C_n$ to $U_\varepsilon(M)\cap\mathcal{M}_{[n]}$ isometrically. Corollary 1. Let $n\geqslant3$ be a positive integer, let $N=n(n-1)/2$, let ${C\subset\mathbb{R}^N}$ be a metric cone and $\pi\colon C\to\mathcal{M}_{[n]}$ be the canonical projection. Let $M\in\mathcal{M}_{[n]}$ be a totally discrete and totally asymmetric space, and let $w\in\pi^{-1}(M)$. Fix $\varepsilon\in(0,s(M)/8]$ such that $\varepsilon<e(M)/8$, and let $U_\varepsilon(w)\subset\mathbb{R}^N$ be the corresponding open ball in $\mathbb{R}^N$. Then the restriction $\pi$ to $U_\varepsilon(w)\cap C$ is isometric. Moreover, if $M$ is generic, that is, $t(M)$ is also strictly positive, and $\varepsilon\leqslant t(M)/6$, then $U_\varepsilon(w)$ lies in the interior of $C$. Proof. Except for the last assertion, this immediately follows from Theorem 2 and the reasoning after it. We prove the last assertion.
We need to show that every $v\in U_\varepsilon(w)$ lies in the interior of $C$, that is, all the coordinates of $v$ are strictly positive and all triangle inequalities are strict. Since $|vw|<\varepsilon$, we have $|v_{ij}-w_{ij}|<2\varepsilon$ for any $i$ and $j$, $1\leqslant i<j\leqslant n$. Since $\varepsilon\leqslant s(M)/8$, it follows that
$$
\begin{equation*}
v_{ij}>w_{ij}-2\varepsilon\geqslant s(M)-2\varepsilon\geqslant8\varepsilon-2\varepsilon=6\varepsilon>0
\end{equation*}
\notag
$$
for any distinct $i,j\in\{1,\dots,n\}$. Thus, all the coordinates of $v$ are strictly positive.
Further, for any pairwise distinct $i,j,k\in\{1,\dots,n\}$ we have
$$
\begin{equation*}
\begin{aligned} \, v_{ij}+v_{jk}-v_{ik} &>w_{ij}-2\varepsilon+w_{jk}-2\varepsilon-(w_{ik}+2\varepsilon)=w_{ij}+w_{jk}-w_{ik}-6\varepsilon \\ &\geqslant t(M)-6\varepsilon\geqslant6\varepsilon-6\varepsilon=0. \end{aligned}
\end{equation*}
\notag
$$
Thus all triangle inequalities in $v$ are strict. The proof is complete.
§ 3. An isometric embedding of a bounded metric space in the class $\operatorname{\mathcal{G\!H}}$ As a consequence of Theorem 2, we prove the universality of the Gromov-Hausdorff metric class for bounded metric spaces. Theorem 3. Let $X$ be a bounded metric space of cardinality $n\geqslant 3$. Then $X$ can be embedded in $\operatorname{\mathcal{G\!H}}_n$ isometrically. Proof. This result was proved in [20] for finite $n$. So we assume that $n$ is an infinite cardinal number. Recall that in this case $\mathcal{N}=n$.
Fix an enumeration $\eta$ of $X$, set $x_i=\eta(i)$ and define a map $f\colon X\to\mathbb{R}^n$ by setting $f(x_i)_j=|x_ix_j|$.
Lemma 1. The map $f$ is isometric with respect to the extended metric on $\mathbb{R}^n$ given by $|xy|\,{=}\sup_i|x_i\,{-}\,y_i|$. Proof. On the one hand $\bigl||x_px_j|-|x_qx_j|\bigr|\,{\leqslant}\,|x_px_q|$ for every $i$ and so
$$
\begin{equation*}
\bigl|f(x_p)f(x_q)\bigr|=\sup_j\bigl||x_px_j|-|x_qx_j|\bigr|\leqslant|x_px_q|.
\end{equation*}
\notag
$$
On the other hand equality is attained for $j=p$ and $j=q$. The proof is complete. The map $f$ is called the Kuratowski embedding (see [21]). For similar examples of its use, see [22] and [20]. Since $n$ is infinite, we can assume that the Kuratowski embedding maps $X$ to $\mathbb{R}^\mathcal{N}$. Let $d$ denote the diameter of $X$. Consider a totally discrete and totally asymmetric space $M$ such that $s(M)>8d$ and $e(M)\,{>}\,8d$. Let $w\in\pi^{-1}(M)$ and set $Z=w+f(X)\subset\mathbb{R}^\mathcal{N}$. Since translations preserve distances in $\mathbb{R}^\mathcal{N}$, we conclude that $Z\subset\mathbb{R}^\mathcal{N}$ is isometric to $X$. Take $\varepsilon>d$ that is smaller than $s(M)/8$ and $e(M)/8$. Then $Z\subset U_\varepsilon:=U_\varepsilon(w)\cap C_n$. Finally, we use the canonical projection $\pi\colon U_\varepsilon\to\operatorname{\mathcal{G\!H}}_{[n]}$, which is isometric by Theorem 2. The proof is complete.
|
|
|
Bibliography
|
|
|
1. |
F. Hausdorff, Grundzüge der Mengenlehre, Veit & Comp., Leipzig, 1914, viii+476 pp. |
2. |
D. A. Edwards, “The structure of superspace”, Studies in topology (Univ. North Carolina, Charlotte, NC 1974), Academic Press, New York, 1975, 121–133 |
3. |
M. Gromov, “Groups of polynomial growth and expanding maps”, Inst. Hautes Études Sci. Publ. Math., 53 (1981), 53–78 |
4. |
A. O. Ivanov, N. K. Nikolaeva and A. A. Tuzhilin, “The Gromov-Hausdorff metric on the space of compact metric spaces is strictly intrinsic”, Mat. Zametki, 100:6 (2016), 947–950 ; English transl. in Math. Notes, 100:6 (2016), 883–885 |
5. |
A. O. Ivanov and A. A. Tuzhilin, “Isometry group of Gromov-Hausdorff space”, Mat. Vesnik, 71:1–2 (2019), 123–154 |
6. |
D. Burago, Yu. Burago and S. Ivanov, A course in metric geometry, Grad. Stud. Math., 33, Amer. Math. Soc., Providence, RI, 2001, xiv+415 pp. |
7. |
A. O Ivanov and A. A. Tuzhilin, Geometry of Hausdorff and Gromov-Hausdorff distances: The case of compact spaces, Board of Trustees of the Faculty of Mechanics and Mathematics of Moscow State University, Moscow, 2017, 111 pp. (Russian) |
8. |
D. Jansen, Notes on pointed Gromov-Hausdorff convergence, 2017, arXiv: 1703.09595 |
9. |
D. A. Herron, “Gromov-Hausdorff distance for pointed metric spaces”, J. Anal., 24:1 (2016), 1–38 |
10. |
S. I. Borzov, A. O. Ivanov and A. A. Tuzhilin, “Geometry of the Gromov-Hausdorff distance on the class of all metric spaces”, Mat. Sb., 213:5 (2022), 68–87 ; English transl. in Sb. Math., 213:5 (2022), 641–658; Extendability of metric segments in Gromov-Hausdorff distance, arXiv: 2009.00458 |
11. |
S. A. Bogaty and A. A. Tuzhilin, Gromov-Hausdorff class: its completeness and cloud geometry, 2021, arXiv: 2110.06101 |
12. |
A. Ivanov, R. Tsvetnikov and A. Tuzhilin, “Path connectivity of spheres in the Gromov-Hausdorff class”, Topology Appl. (to appear); 2022, arXiv: 2111.06709 |
13. |
P. Ghanaat, Gromov-Hausdorff distance and applications, Summer school “Metric geometry” (Les Diablerets, August 25–30 2013), 2013 https://homeweb.unifr.ch/ghanaatp/pub/gromov-hausdorff.pdf |
14. |
D. S. Grigor'ev, A. O. Ivanov and A. A. Tuzhilin, “Gromov-Hausdorff distance to simplexes”, Chebyshevskii Sb., 20:2 (2019), 108–122 ; English transl., (2019), arXiv: 1906.09644 |
15. |
A. Ivanov, S. Iliadis and A. Tuzhilin, Realizations of Gromov-Hausdorff distance, 2016, arXiv: 1603.08850 |
16. |
S. Chowdhury and F. Memoli, Explicit geodesics in Gromov-Hausdorff space, 2016, arXiv: 1603.02385 |
17. |
A. O. Ivanov and A. A. Tuzhilin, “Local structure of Gromov-Hausdorff space around generic finite metric spaces”, Lobachevskii J. Math., 38:6 (2017), 998–1006 ; Local structure of Gromov-Hausdorff space near finite metric spaces in general position, 2016, arXiv: 1611.04484 |
18. |
A. M. Filin, “Local geometry of the Gromov-Hausdorff metric space and totally asymmetric finite metric spaces”, Fundam. Prikl. Mat., 22:6 (2019), 263–272 ; English transl. in J. Math. Sci. (N.Y.), 259:5 (2021), 754–760 |
19. |
S. Roman, Lattices and ordered sets, Springer, New York, 2008, xvi+305 pp. |
20. |
S. Iliadis, A. Ivanov and A. Tuzhilin, “Local structure of Gromov-Hausdorff space, and isometric embeddings of finite metric spaces into this space”, Topology Appl., 221 (2017), 393–398 |
21. |
C. Kuratowski, “Quelques problèmes concernant les espaces métriques non-séparables”, Fundamenta Math., 25 (1935), 534–545 |
22. |
A. O. Ivanov and A. A. Tuzhilin, “One-dimensional Gromov minimal filling problem”, Mat. Sb., 203:5 (2012), 65–118 ; English transl. in Sb. Math., 203:5 (2012), 677–726 |
Citation:
A. O. Ivanov, A. A. Tuzhilin, “Isometric embeddings of bounded metric spaces in the Gromov-Hausdorff class”, Mat. Sb., 213:10 (2022), 90–107; Sb. Math., 213:10 (2022), 1400–1414
Linking options:
https://www.mathnet.ru/eng/sm9729https://doi.org/10.4213/sm9729e https://www.mathnet.ru/eng/sm/v213/i10/p90
|
Statistics & downloads: |
Abstract page: | 261 | Russian version PDF: | 32 | English version PDF: | 55 | Russian version HTML: | 151 | English version HTML: | 53 | References: | 36 | First page: | 8 |
|