$a_{i_{3}}\in A_{i_{3}}$ for which $|a_{i_{2}}a_{i_{3}}|<\varepsilon/8$.
Continuing this process, we construct a sequence
$\omega=(a_{i_{1}}=a_{1},a_{i_{2}},a_{i_{3}},\ldots)$, $a_{i_{k}}\in
A_{i_{k}}$, for which $|a_{i_{k-1}}a_{i_{k}}|<\varepsilon/2^{k}$ for $k\geq
3$. By the triangle inequality, for any $p,q\in{\mathbb{N}}$, $2\leq p\leq q$,
we have $|a_{i_{p}}a_{i_{q}}|<\varepsilon/2^{p}$, therefore, the sequence
$\omega$ is fundamental. On the other hand, for any $p,q\in{\mathbb{N}}$ we
have $|a_{i_{p}}a_{i_{q}}|<d_{1}(\Omega)+\varepsilon/2$, hence
$d_{1}(\omega)\leq d_{1}(\Omega)+\varepsilon/2<d_{1}(\Omega)+\varepsilon$. ∎

Example 5.15 demonstrates that for a complete $X$ a upper limit can be empty.
However, for a fundamental sequence $A_{k}$ this is no longer the case.

######  Proposition 5.35.

Let $X$ be a complete space and $A_{k}\in\mathcal{P}_{0}(X)$ be a fundamental
sequence, then $\limsup A_{k}\neq\emptyset$.

###### Proof.

We choose an arbitrary $a_{1}\in A_{1}$, then, by Proposition 5.34, there
exists a fundamental sequence $(a_{i_{1}}=a_{1},a_{i_{2}},a_{i_{3}},\ldots)$
such that $a_{i_{k}}\in A_{i_{k}}$. Since $X$ is a complete space, this
sequence converges to some $x\in X$. Proposition 5.12 implies that
$x\in\limsup A_{k}$, therefore $\limsup A_{k}\neq\emptyset$. ∎

Now we will give an analogue of Proposition 5.28.

######  Theorem 5.36.

Let $X$ be an arbitrary metric space, $A_{k}\in\mathcal{P}_{0}(X)$ a
fundamental sequence, and $A=\limsup A_{k}$ _(_ possibly empty _)_. Then for
any $\varepsilon>0$ there exists $n$ such that for any $k\geq n$

  1. (1)

$A\subset U_{\varepsilon}(A_{k})$_;_

  2. (2)

if the space $X$ is complete, then $A\neq\emptyset$ and $A_{k}\subset
U_{\varepsilon}(A)$.

Therefore, in complete $X$ we have $A_{k}\xrightarrow{d_{H}}A$ and, hence,
there exists $\lim A_{k}$.

###### Proof.

Since the sequence $\Omega^{\prime}=(A_{1},A_{2},\ldots)$ is fundamental,
Proposition 5.33 implies that $d_{k}(\Omega^{\prime})\to 0$. Choose $n$ such
that $d_{n}(\Omega^{\prime})<\varepsilon/2$. Consider an arbitrary $k\geq n$
and put $\Omega=(A_{k},A_{k+1},\ldots)$. Since the sequence
$d_{i}(\Omega^{\prime})$ is monotonic, we have $d_{1}(\Omega)<\varepsilon/2$.

(1) If $A=\emptyset$, then the inclusion is proved. Now let $A\neq\emptyset$.
We choose an arbitrary $a\in A$, then, by Corollary 5.13, there exists a
sequence $\omega=(a_{i_{1}},a_{i_{2}},\ldots)$ converging to $a$ so that for
some $p\in{\mathbb{N}}$ we have $|a_{i_{p}}a|<\varepsilon/2$. On the other
hand, since $d_{1}(\Omega)<\varepsilon/2$, then
$d_{H}(A_{k},A_{i_{p}})<\varepsilon/2$, therefore there exists $a_{k}\in
A_{k}$ for which $|a_{k}a_{i_{p}}|<\varepsilon/2$. By the triangle inequality,
$|a_{k}a|<\varepsilon$, therefore, because $a$ is arbitrary, we have $A\subset
U_{\varepsilon}(A_{k})$.

(2) Let us apply Proposition 5.34 to the sequence $\Omega$. By this
proposition, each $a_{k}\in A_{k}$ is included in some fundamental sequence
$\omega$ for which $d_{1}(\omega)<d_{1}(\Omega)+\varepsilon/2<\varepsilon$.
Due to the completeness of the space $X$ and Proposition 5.12, the sequence
$\omega$ converges to some element $a\in A$, hence, taking into account the
previous estimate on $d_{1}(\omega)$, we get $|a_{k}a|<\varepsilon$, therefore
$A_{k}\subset U_{\varepsilon}(A)$. The existence of the limit follows from
Theorem 5.23. ∎

######  Corollary 5.37.

A metric space $X$ is complete if and only if $\mathcal{H}(X)$ is complete.

###### Proof.

The completeness of $\mathcal{H}(X)$ for complete $X$ is proved in Theorem
5.36. Conversely, let $\mathcal{H}(X)$ be a complete space. Consider an
arbitrary fundamental sequence $a_{k}$ in $X$; then, due to the isometry of
the mapping $x\mapsto\\{x\\}$, the sequence
$A_{k}=\\{a_{k}\\}\in\mathcal{H}(X)$ is also fundamental. Since
$\mathcal{H}(X)$ is complete, the sequence $A_{k}$ converges to some
$A\in\mathcal{H}(X)$. However, by Corollary 5.21, the sequence $a_{k}$ also
converges. ∎

####  5.2.3 Inheritance of total boundedness and compactness

The purpose of this section is to prove the following theorem.

######  Theorem 5.38.

Let $X$ be an arbitrary metric space. Then the following properties are
simultaneously present or not in both $X$ and $\mathcal{H}(X)$_:_

  1. (1)

completeness _(_ Khan _)_ ,

  2. (2)

total boundedness,

  3. (3)

compactness _(_ Hausdorff, Blaschke _)_.

###### Proof.

(1) This is Corollary 5.37.

(2) Let $X$ be totally bounded. The total boundedness of $\mathcal{H}(X)$
immediately follows from the following lemma and problem.

######  Lemma 5.39.

Let $W$ be an arbitrary metric space, $\varepsilon>0$, and $Y\subset W$ be
some $\varepsilon$-net, then for any $\delta>\varepsilon$ the set
$\mathcal{P}_{0}(Y)$ is a $\delta$-net in $\mathcal{P}_{0}(W)$.

###### Proof.

Indeed, we choose an arbitrary $F\in\mathcal{P}_{0}(W)$ and put $M=\\{y\in
Y:|yF|<\varepsilon\\}$, thus for every $y\in M$ there exists $w\in F$ such
that $|yw|<\varepsilon$, therefore, $M\subset U_{\varepsilon}(F)$.

Further, since $Y$ is an $\varepsilon$-net for $W$, then for every $w\in F$
there exists $y\in Y$ for which $|yw|<\varepsilon$, hence
$|yF|\leq|yw|<\varepsilon$ and, therefore, $y\in M$. In particular,
$M\neq\emptyset$, i.e., $M\in\mathcal{P}_{0}(W)$. Since $w$ is arbitrary, we
get $F\subset U_{\varepsilon}(M)$, therefore,
$d_{H}(F,M)\leq\varepsilon<\delta$. ∎

######  Problem 5.9.

If $W$ is a metric space, $Y\subset W$ is an $\varepsilon$-net, and $Z\subset
W$ is not empty. Then $Z$ contains an $(2\varepsilon)$-net $S$ such that
$\\#S\leq\\#Y$.

Conversely, let $\mathcal{H}(X)$ be totally bounded. The total boundedness of
$X$ follows from the following lemma.

######  Lemma 5.40.

Let $W$ be an arbitrary metric space, $\varepsilon>0$, and
$\mathcal{Y}\subset\mathcal{H}(W)$ be some $\varepsilon$-net. Denote by
$M\subset W$ the set obtained by choosing at each element $Y\in\mathcal{Y}$
any one point $p(Y)$. Then $M$ is an $\varepsilon$-net in $W$ _(_ of the same
cardinality as $\mathcal{Y}$_)_.

###### Proof.

We choose an arbitrary $w\in W$, then there exists $Y\in\mathcal{Y}$ such that
$d_{H}\bigl{(}\\{w\\},Y\bigr{)}<\varepsilon$. Hence $Y\subset
U_{\varepsilon}(w)$ and, therefore, $\bigl{|}p(Y)w\bigr{|}<\varepsilon$. ∎

(3) This follows from the previous section and Theorem 2.24. ∎

###  5.3 Inheritance of geodesic

In this section we present the results from [4].

######  Theorem 5.41.

Let $X$ be a compact metric space, then $\mathcal{H}(X)$ is geodesic if and
only if $X$ is geodesic.

###### Proof.

First, let $X$ be a geodesic space. To prove that $\mathcal{H}(X)$ is
geodesic, we use Theorems 5.38 and 3.47. The first of them claims that
$\mathcal{H}(X)$ is compact and, therefore, complete; the second is that
$\mathcal{H}(X)$ is geodesic if for any its elements there exists a midpoints.
That is what we will prove.

Consider arbitrary $A,B\in\mathcal{H}(X)$, $r:=d_{H}(A,B)$, put
$C=B_{r/2}(A)\cap B_{r/2}(B)$, and show that $C$ is a midpoint between $A$ and
$B$.

Indeed, $C$ is closed as the intersection of closed sets. We show that
$C\neq\emptyset$. Choose an arbitrary $a\in A$. By Proposition 5.5, $A\subset
B_{r}(B)$, therefore, since $B$ is compact, there exists $b\in B$ such that
$|ab|\leq r$. Since the space $X$ is geodesic, for the points $a$ and $b$
there is a midpoint $c$, then $c\in C$, which proves the nonemptiness of $C$
and, at the same time, that $A\subset B_{r/2}(C)$. In addition, $C\subset
B_{r/2}(A)$ by construction, hence $d_{H}(A,C)\leq r/2$. Similarly,
$d_{H}(B,C)\leq r/2$. Since $r=d_{H}(A,B)\leq d_{H}(A,C)+d_{H}(C,B)$, then
$d_{H}(A,C)=d_{H}(C,B)=r/2$, so $C$ is a midpoint between $A$ and $B$. We
again use Theorem 3.47 and conclude that the space $\mathcal{H}(X)$ is
geodesic.

Conversely, let the space $\mathcal{H}(X)$ be geodesic. We choose arbitrary
points $a,b\in X$, $r:=|ab|$, then, due to the geodesicity of
$\mathcal{H}(X)$, it contains $C$, which is a midpoint between $\\{a\\}$ and
$\\{b\\}$. By Items (1) of Problem 5.1, we have
$d_{H}\bigl{(}\\{a\\},\\{b\\}\bigr{)}=r$, so
$d_{H}\bigl{(}\\{a\\},C\bigr{)}=d_{H}\bigl{(}C,\\{b\\}\bigr{)}=r/2$, hence
$C\subset B_{r/2}(a)\cap B_{r/2}(b)$. We choose an arbitrary point $c\in C$,
then $|ac|\leq r/2$ and $|cb|\leq r/2$; since $r=|ab|\leq|ac|+|cb|$, then
$|ac|=|cb|=r/2$ and, therefore, $c\in X$ is a midpoint between $a$ and $b$. It
remains to use Theorem 3.47. ∎

We give a few examples to demonstrate that for the space $\mathcal{H}(X)$ was
geodesic, neither the total boundedness of $X$, nor its completeness is
sufficient individually.

######  Problem 5.10.

Denote by $X$ a subset of the space $\mathbb{R}^{3}$, which in the standard
Cartesian coordinates has the form

$X=\\{x^{2}+y^{2}<1,\,z\leq
1\\}\cup\\{x^{2}+y^{2}=1,\,z=-1,\,x\in{\mathbb{Q}}\\}\cup\\{x^{2}+y^{2}=1,\,z=1,\,x\in\mathbb{R}\setminus{\mathbb{Q}}\\}.$

Next, put $A=\\{x^{2}+y^{2}=1,\,z=-1,\,x\in{\mathbb{Q}}\\}$ and
$B=\\{x^{2}+y^{2}=1,\,z=1,\,x\in\mathbb{R}\setminus{\mathbb{Q}}\\}$. Show that
$X$ is a geodesic space, but $A$ and $B$ are not connected by a shortest curve
(there is no midpoint between them), so $\mathcal{H}(X)$ is not geodesic.

######  Problem 5.11.

Consider the square $X=[-1,1]\times[-1,1]$ and introduce the following
distance function on $X$:

$d\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}=|x-x^{\prime}|+\min\\{(1-y)+(1-y^{\prime}),(y+1)+(y^{\prime}+1)\\}.$

Show that $(X,d)$ is a complete geodesic space, $A=[-1,1]\times{-1}$ and
$B=[-1,1]\times\\{1\\}$ are compacts such that there is midpoint between them
in $\mathcal{K}(X)$, i.e., $\mathcal{K}(X)$ is not geodesic.

######  Problem 5.12.

Consider two segments $I_{0}=[0,1]\times{0}$ and $I_{1}=[0,1]\times\\{1\\}$ in
the Euclidean plane $\mathbb{R}^{2}$, and let $A\subset I_{0}$ be the subset
of all points with rational abscissae, and $B\subset I_{1}$ the subset of all
points with irrational abscissae. For each $a\in A$ and $b\in B$ we denote by
$r(a,b)$ the distance between $a$ and $b$ in $\mathbb{R}^{2}$. Now, for each
$a\in A$, $b\in B$ consider a circle $S(a,b)$ or the length $3$, and denote by
the same $a$ and $b$ some points of $S(a,b)$ bounding an arc $\alpha(a.b)$ of
the length $r(a,b)$. Let $C(a,b)\in S(a,b)$ be the middle point of the act
complement to $\alpha(a,b)$. Denote by $X$ the quotient space obtained from
all $S(a,b)$ by identifying their points $C(a,b)$. Also denote by $A$ and $B$
the subsets of $X$ consisting of all points $a$ and all points $b$,
respectively. Prove that $X$ is complete and geodesic, $A,B\in\mathcal{H}(X)$,
however, there is no a midpoint between $A$ and $B$, thus, $\mathcal{H}(X)$ is
complete but not geodesic.

## References to Chapter 5

  * [1] D.Burago, Yu.Burago, S.Ivanov, _A Course in Metric Geometry_. Graduate Studies in Mathematics, vol.33, A.M.S., Providence, RI, 2001.
  * [2] S.Nadler, _Hyperspaces of Sets_ , 1978.
  * [3] A.Illanes, S.Nadler, _Hyperspaces_ , 1999.
  * [4] Bryant V.W. _The convexity of the subset space of a metric space_ , Compositio Mathematica, 1970, vol. 22, N 4, p. 383–385.

### Exercises to Chapter 5

######  Exercise 5.1.

Prove the following statements for an arbitrary metric space $X$.

  1. (1)

Let $f\colon X\to\mathcal{H}(X)$ be given by the formula $f\colon
x\mapsto\\{x\\}$, then $f$ is an isometric embedding.

  2. (2)

For any $A,B\in\mathcal{P}_{0}(X)$ we have
$d_{H}(A,B)=d_{H}(A,{\bar{B}})=d_{H}({\bar{A}},B)=d_{H}({\bar{A}},{\bar{B}})$.

  3. (3)

For any $A,B\in\mathcal{P}_{0}(X)$ we have $d_{H}(A,B)=0$ if and only if
${\bar{A}}={\bar{B}}$.

  4. (4)

If $Y\subset X$ is an $\varepsilon$-net in $A\subset X$, then
$d_{H}(A,Y)\leq\varepsilon$.

######  Exercise 5.2.

Prove that for $A,B\in\mathcal{K}(X)$ there exist $a\in A$ and $b\in B$ such
that $d_{H}(A,B)=|ab|$. Is it possible to change $\mathcal{K}(X)$ with
$\mathcal{H}(X)$?

######  Exercise 5.3.

Let $X$ be an arbitrary metric space and
$A,B,A^{\prime},B^{\prime}\in\mathcal{H}(X)$ such that $A^{\prime}\subset A$
and $B^{\prime}\subset B$. Prove that $d_{H}(A\cup B^{\prime},B\cup
A^{\prime})\leq d_{H}(A,B)$.

######  Exercise 5.4.

Let $X$ be an arbitrary metric space and $A,B,C\in\mathcal{H}(X)$ such that
$C\subset B$. Prove that $d_{H}(A,A\cup C)\leq d_{H}(A,B)$.

######  Exercise 5.5.

Prove that $\liminf A_{i}$ is a closed subset of $X$.

######  Exercise 5.6.

Let $\ell_{2}$ denote the space of all sequences $(x_{1},x_{2},\ldots)$ of
real numbers such that $\sum_{i=1}^{\infty}x^{2}<\infty$. For
$\xi=(x_{1},x_{2},\ldots)\in\ell_{2}$ and
$\xi^{\prime}=(x^{\prime}_{1},x^{\prime}_{2},\ldots)\in\ell_{2}$ we put
$d(\xi,\xi^{\prime})^{2}={\sum_{i=1}^{\infty}(x_{i}-x^{\prime}_{i})^{2}}$.
Prove that $d$ is a metric on $\ell_{2}$, and that $(\ell_{2},d)$ is a
complete metric space.

######  Exercise 5.7.

Denote by $e_{i}\in\ell_{2}$ the sequence $(x_{1},x_{2},\ldots)$ such that
$x_{i}=1$ and $x_{j}=0$ for all $j\neq i$. Prove that
$A=\\{e_{i}\\}_{i=1}^{\infty}$ is a closed subset of $\ell_{2}$, thus
$A\in\mathcal{H}(\ell_{2})$.

######  Exercise 5.8.

Let $X={\mathbb{N}}$, and define two metrics on $X$: $d^{1}(x,y)=1$ for any
$x\neq y$, and $d^{2}(x,y)=\bigl{|}\frac{1}{x}-\frac{1}{y}\bigr{|}$ for any
$x,y$. Then the corresponding metric topologies are both discrete. Prove that
the corresponding Hausdorff metric generates non-homeomorphic topologies on
$\operatorname{CL}(X)$.

######  Exercise 5.9.

Suppose that in a sequence $A_{i}\in\mathcal{H}(X)$ all $A_{i}$ are connected,
$A_{i}\to A\in\mathcal{H}(X)$, and $\liminf A_{i}\neq\emptyset$. Prove that
$\limsup A_{i}$ is connected.

######  Exercise 5.10.

Denote by $X$ a subset of the space $\mathbb{R}^{3}$, which in the standard
Cartesian coordinates has the form

$X=\\{x^{2}+y^{2}<1,\,z\leq
1\\}\cup\\{x^{2}+y^{2}=1,\,z=-1,\,x\in{\mathbb{Q}}\\}\cup\\{x^{2}+y^{2}=1,\,z=1,\,x\in\mathbb{R}\setminus{\mathbb{Q}}\\}.$

Next, put $A=\\{x^{2}+y^{2}=1,\,z=-1,\,x\in{\mathbb{Q}}\\}$ and
$B=\\{x^{2}+y^{2}=1,\,z=1,\,x\in\mathbb{R}\setminus{\mathbb{Q}}\\}$. Show that
$X$ is a geodesic space, but $A$ and $B$ are not connected by a shortest curve
(there is no midpoint between them), so $\mathcal{H}(X)$ is not geodesic.

######  Exercise 5.11.

Consider the square $X=[-1,1]\times[-1,1]$ and introduce the following
distance function on $X$:

$d\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}=|x-x^{\prime}|+\min\\{(1-y)+(1-y^{\prime}),(y+1)+(y^{\prime}+1)\\}.$

Show that $(X,d)$ is a complete geodesic space, $A=[-1,1]\times{-1}$ and
$B=[-1,1]\times\\{1\\}$ are compacts such that there is no midpoint between
them in $\mathcal{K}(X)$, i.e., $\mathcal{K}(X)$ is not geodesic.

######  Exercise 5.12.

Consider two segments $I_{0}=[0,1]\times{0}$ and $I_{1}=[0,1]\times\\{1\\}$ in
the Euclidean plane $\mathbb{R}^{2}$, and let $A\subset I_{0}$ be the subset
of all points with rational abscissae, and $B\subset I_{1}$ the subset of all
points with irrational abscissae. For each $a\in A$ and $b\in B$ we denote by
$r(a,b)$ the distance between $a$ and $b$ in $\mathbb{R}^{2}$. Now, for each
$a\in A$, $b\in B$ consider a circle $S(a,b)$ or the length $3$, and denote by
the same $a$ and $b$ some points of $S(a,b)$ bounding an arc $\alpha(a.b)$ of
the length $r(a,b)$. Let $C(a,b)\in S(a,b)$ be the middle point of the act
complement to $\alpha(a,b)$. Denote by $X$ the quotient space obtained from
all $S(a,b)$ by identifying their points $C(a,b)$. Also denote by $A$ and $B$
the subsets of $X$ consisting of all points $a$ and all points $b$,
respectively. Prove that $X$ is complete and geodesic, $A,B\in\mathcal{H}(X)$,
however, there is no a midpoint between $A$ and $B$, thus, $\mathcal{H}(X)$ is
complete but not geodesic.

##  Chapter 6 Gromov–Hausdorff Distance.

  * Schedule.

Realization of a pair of metric space, Gromov–Hausdorff distance, admissible
metric on disjoin union of metric spaces, calculation of Gromov–Hausdorff
distance in terms of admissible metrics, triangle inequality for
Gromov–Hausdorff distance, positive definiteness of Gromov–Hausdorff distance
for isometry classes of compact spaces, counterexample for boundedly compact
spaces, Gromov–Hausdorff distance for separable spaces in terms of their
isometric images in $\ell_{\infty}$, relations, distortion of a relation
between metric spaces, correspondences, Gromov–Hausdorff distance in terms of
correspondences, $\varepsilon$-isometries and Gromov–Hausdorff distance,
irreducible correspondences between sets, existence of irreducible
correspondences, irreducible correspondences as bijections of partitions of
sets, Gromov–Hausdorff distance in terms of irreducible correspondences,
examples: Gromov–Hausdorff distance between $2$\- or $3$-point metric spaces,
simple general properties of Gromov–Hausdorff distance, Gromov–Hausdorff
convergence, inheritance of metric and topological properties while
Gromov–Hausdorff convergence.

In this section, we will study the Gromov–Hausdorff distance, see [1] and [2]
for more details. All metric spaces are supposed to be nonempty.

######  Construction 6.1.

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}$, which are isometric respectively to $X$ and $Y$, will be called
_a realization of the pair $(X,Y)$_. We put

$d_{GH}(X,Y)=\inf\bigl{\\{}r\in\mathbb{R}:\text{there exists a realization
$(X^{\prime},Y^{\prime},Z)$ of $(X,Y)$ such that
$d_{H}(X^{\prime},Y^{\prime})\leq r$}\bigr{\\}}.$

######  Remark 6.1.

The value $d_{GH}(X,Y)$ is evidently non-negative, symmetric, and
$d_{GH}(X,X)=0$ for any metric space $X$. Thus, $d_{GH}$ is a distance
function on each set of metric spaces.

######  Definition 6.2.

The value $d_{GH}(X,Y)$ from Construction 6.1 is called _the Gromov–Hausdorff
distance_ between the metric spaces $X$ and $Y$.

######  Problem 6.1.

Prove that for any metric spaces $X$ and $Y$ there exists a realization of
$(X,Y)$.

######  Remark 6.3.

In some monographs the Gromov–Hausdorff distance $d_{GH}(X,Y)$ is defined as
the infimum of the values $d_{H}(X^{\prime},Y^{\prime})$ over all realizations
$(X^{\prime},Y^{\prime},Z)$ of the pair $(X,Y)$. However, we give such, at
first glance, a more technically complicated definition of $d_{GH}$, to avoid
the Cantor paradox, because the family of all realizations is no longer a set.
Introducing $r$ and talking about _the existence of a realization_ , we
thereby get rid of the need to consider all the realizations.

######  Notation.

In what follows, it will sometimes be necessary for us to explicitly indicate
the space $X$ in which a particular metric is considered, as well as the
corresponding Hausdorff metric. Thus, the distance between points
$x,x^{\prime}\in X$ will sometimes be denoted by $|xx^{\prime}|_{X}$, and the
corresponding Hausdorff distance between nonempty subsets $A$ and $B$ of the
space $X$ by $d_{H}^{X}(A,B)$. In addition, if $\rho$ is some metric on $X$,
then the Hausdorff distance generated by this metric will sometimes be denoted
by $\rho_{H}$.

It turns out that, to define the Gromov–Hausdorff distance, it suffices to
consider only metric spaces of the form $(X\sqcup Y,\rho)$, where $\rho$
extends the original metrics of $X$ and $Y$. Such $\rho$ will be called _an
admissible metric for $X$ and $Y$_, and the set of all admissible metrics for
given $X$ and $Y$ will be denoted by $\mathcal{D}(X,Y)$.

######  Problem 6.2.

Prove that for any metric spaces $X$ and $Y$ there exists at least one
admissible metric, i.e., the set $\mathcal{D}(X,Y)$ is not empty.

######  Theorem 6.4.

For any metric spaces $X$ and $Y$, we have

(6.1)
$d_{GH}(X,Y)=\inf\bigl{\\{}\rho_{H}(X,Y):\rho\in\mathcal{D}(X,Y)\bigr{\\}}.$

###### Proof.

Denote by $d^{\prime}_{GH}(X,Y)$ the right hand side of the equation (6.1).
Then $d_{GH}(X,Y)\leq d^{\prime}_{GH}(X,Y)$, because for every
$\rho\in\mathcal{D}(X,Y)$ and $Z=(X\sqcup Y,\rho)$, the triple $(X,Y,Z)$ is a
realization of the pair $(X,Y)$ with the same Hausdorff distance
$\rho_{H}(X,Y)$. We now prove the inverse inequality.

By Construction 6.1, for any $\varepsilon>0$ there exists a realization
$(X^{\prime},Y^{\prime},Z)$ of the pair $(X,Y)$ such that

$d_{H}(X^{\prime},Y^{\prime})\leq d_{GH}(X,Y)+\varepsilon.$

If $X^{\prime}$ and $Y^{\prime}$ do not intersect each other, then we restrict
the metric from $Z$ to $X^{\prime}\sqcup Y^{\prime}$, and, after identifying
$X^{\prime}$ and $Y^{\prime}$ with $X$ and $Y$, respectively, we obtain an
admissible metric $\rho$ on $X\sqcup Y$ for which $\rho_{H}(X,Y)\leq
d_{GH}(X,Y)+\varepsilon$. If $X^{\prime}\cap Y^{\prime}\neq\emptyset$, we
replace $Z$ by $Z\times\mathbb{R}$ with the metric
$\bigl{|}(z,t)(z^{\prime},s)\bigr{|}=|zz^{\prime}|+|ts|$, also replace
$X^{\prime}$ and $Y^{\prime}$ by the sets
$X^{\prime\prime}=X^{\prime}\times\\{0\\}$ and
$Y^{\prime\prime}=Y^{\prime}\times\\{\varepsilon\\}$, respectively, then
$(X^{\prime\prime},Y^{\prime\prime},Z\times\mathbb{R})$ is a realization of
the $(X,Y)$ such that $X^{\prime\prime}\cap Y^{\prime\prime}=\emptyset$,
$d_{H}(X^{\prime\prime},Y^{\prime\prime})\leq d_{GH}(X,Y)+2\varepsilon$, and
aging we can restrict the metric of $Z\times\mathbb{R}$ to
$X^{\prime\prime}\sqcup Y^{\prime\prime}$, identify $X$ with
$X^{\prime\prime}$, $Y^{\prime\prime}$ with $Y$, and obtain an admissible
metric $\rho$ with $\rho_{H}(X,Y)\leq d_{GH}(X,Y)+2\varepsilon$. Since
$\varepsilon$ is arbitrary, we get $d^{\prime}_{GH}(X,Y)\leq d_{GH}(X,Y)$. ∎

######  Remark 6.5.

If $X$ and $Y$ are subsets of some metric space, then $d_{GH}(X,Y)\leq
d_{H}(X,Y)$. In particular, if $d_{H}(X,Y)=0$, then $d_{GH}(X,Y)=0$, so the
Gromov–Hausdorff distance, like the Hausdorff distance, is not positively
defined: for example, the Gromov–Hausdorff distance between the segment
$[0,1]$ and the interval $(0,1)$ vanishes. However, if we restrict ourselves
to compact metric spaces, then $d_{GH}(X,Y)=0$ if and only if $X$ and $Y$ are
isometric (see below for the proof).

######  Proposition 6.6.

The function $d_{GH}$ satisfies the triangle inequality.

###### Proof.

Choose arbitrary metric spaces $X$, $Y$, and $Z$. We have to show that
$d_{GH}(X,Z)\leq d_{GH}(X,Y)+d_{GH}(Y,Z)$.

Choose any admissible metrics $\mu\in\mathcal{D}(X,Y)$ and
$\nu\in\mathcal{D}(Y,Z)$. Recall that in Example 2.15 we have defined the
gluing $U\sqcup_{f}V$ of metric spaces $U$ and $V$ over a mapping $f\colon
W\to V$, where $W\subset U$. Also, Problem 2.15 states that if $f$ is
isometric, then the restrictions of the metric of $U\sqcup_{f}V$ to $U$ and
$V$ coincides with the original ones. We apply this result to $U=X\sqcup Y$
and $V=Y\sqcup Z$ with the metrics $\mu$ and $\nu$, respectively, and to $W=Y$
and $f=\operatorname{id}\colon Y\to Y\subset Y\sqcup Z$.

Consider the metric space $A=(X\sqcup Y)\sqcup_{f}(Y\sqcup Z)$ with the
corresponding quotient metric $\rho:=\rho_{\sim}$. By Problem 2.15, the
restrictions of the metric $\rho$ from $A$ to $X$ and $Z$ coincide with the
original ones, thus $(X,Z,A)$ is a realization of $(X,Z)$. Also, by definition
of $\rho$, for any $x\in X$ and $z\in Z$ we have
$\rho(x,z)\leq\mu(x,y)+\nu(y,z)$. Let us put $a=\mu_{H}(X,Y)$,
$b=\nu_{H}(Y,Z)$, and choose some $\delta>0$. Then for any $x\in X$ there
exists $y\in Y$ such that $\mu(x,y)<a+\delta/2$; also, for any $y\in Y$ there
exists $z\in Z$ such that $\nu(y,z)<b+\delta/2$, thus for any $x\in X$ there
exists $z\in Z$ and, similarly, for any $z\in Z$ there exists $x\in X$ such
that $\rho(x,z)\leq\mu(x,y)+\nu(y,z)<a+b+\delta$, thus $\rho_{H}(X,Z)\leq
a+b+\delta$. Since $\delta$ is arbitrary, we get
$\rho_{H}(X,Z)\leq\mu_{H}(X,Y)+\nu_{H}(Y,Z)$. Thus,

$d_{GH}(X,Z)=\inf_{d\in\mathcal{D}(X,Z)}d_{H}(X,Z)\leq\inf_{\rho}\rho_{H}(X,Z)\leq\inf_{\mu\in\mathcal{D}(X,Y),\
\nu\in\mathcal{D}(Y,Z)}\bigl{(}\mu_{H}(X,Y)+\nu_{H}(Y,Z)\bigr{)}=\\\
=\inf_{\mu\in\mathcal{D}(X,Y)}\mu_{H}(X,Y)+\inf_{\nu\in\mathcal{D}(Y,Z)}\nu_{H}(Y,Z)=d_{GH}(X,Y)+d_{GH}(Y,Z),$

where the second equality holds because the values we minimize over $\mu$ and
$\nu$ are independent. ∎

Thus, we have shown that on every set of metric spaces, the function $d_{GH}$
is a generalized pseudometric. If the diameters of all spaces in the family
are bounded by the same number, then $d_{GH}$ is a (finite) pseudometric. As
we already noted, $d_{GH}$ is not a metric in general. However, if we restrict
ourselves to compact metric spaces considered upto isometry, then $d_{GH}$
will already be a metric.

######  Proposition 6.7.

For compact metric spaces $X$ and $Y$, it holds $d_{GH}(X,Y)=0$ if and only if
$X$ and $Y$ are isometric.

###### Proof.

If $X$ is isometric to $Y$ then we can take $Z=X^{\prime}=Y^{\prime}=X$, thus
$(Z,X^{\prime},Y^{\prime})$ is a realization of $(X,Y)$, and
$d_{H}(X^{\prime},Y^{\prime})=0$. Now we prove the converse statement.

Consider a sequence of admissible metrics $d^{k}\in\mathcal{D}(X,Y)$ such that
$d^{k}_{H}(X,Y)<1/k$, $k=1,\,2,\ldots$, then for each $x\in X\subset X\sqcup
Y$ there exists $y\in Y\subset X\sqcup Y$ such that $d^{k}(x,y)<1/k$. We
choose any such $y$ and put $I_{k}(x)=y$. Thus, we have constructed a mapping
$I_{k}\colon X\to Y$ (possibly discontinuous). Similarly, we define a mapping
$J_{k}\colon Y\to X$.

From the triangle inequality it follows that for any $x,x^{\prime}\in X$ and
$y,y^{\prime}\in Y$ we have

(6.2)
$\begin{gathered}d^{k}\bigl{(}I_{k}(x),I_{k}(x^{\prime})\bigr{)}<\frac{2}{k}+d^{k}(x,x^{\prime}),\
\
d^{k}\bigl{(}J_{k}(y),J_{k}(y^{\prime})\bigr{)}<\frac{2}{k}+d^{k}(y,y^{\prime}),\\\
d^{k}\bigl{(}x,J_{k}\circ I_{k}(x)\bigr{)}<\frac{2}{k},\ \
d^{k}\bigl{(}y,I_{k}\circ J_{k}(y)\bigr{)}<\frac{2}{k}.\end{gathered}$

Similarly to what was done in the proof of the Arzela–Ascoli theorem, we
construct the “limit” mappings $I\colon X\to Y$ and $J\colon Y\to X$. Namely,
we choose in $X$ a countable everywhere dense subset
$S=\\{x_{1},x_{2},\ldots\\}$; using the Cantor diagonal process, we construct
a subsequence $\\{I_{k_{1}},I_{k_{2}},\ldots\\}$ such that for every $i$ the
sequence $I_{k_{p}}(x_{i})$ converges to some $I(x_{i})\in Y$ (here we use the
compactness of $Y$). The mapping $I$ is $1$-Lipschitz because for every
$x_{i},x_{j}\in S$ we have

$\bigl{|}I(x_{i})I(x_{j})\bigr{|}=d^{k}\bigl{(}I(x_{i}),I(x_{j})\bigr{)}\leq\frac{2}{k}+d^{k}(x_{i},x_{j})=\frac{2}{k}+|x_{i}x_{j}|,$

and since $k$ is arbitrary, we have
$\bigl{|}I(x_{i})I(x_{j})\bigr{|}\leq|x_{i}x_{j}|$. Since $Y$ is complete, by
Lemma 3.48 we can extend $I$ onto the whole $X$ by continuity to a
$1$-Lipschitz mapping (we denote this mapping by the same symbol $I$). We
proceed similarly with the sequence $J_{k}$. Passing to the limit in the last
two inequalities (6.2) as $k\to\infty$, we conclude that for any $x\in X$ and
$y\in Y$ we have

(6.3) $\bigl{|}x\,(J\circ I)(x)\bigr{|}=0,\ \ \bigl{|}y\,(I\circ
J)(y)\bigr{|}=0.$

The relations (6.3) indicates that $I$ and $J$ are mutually inverse
bijections, and the $1$-Lipschitz condition for the both $I$ and $J$
guarantees that them preserve the distance, i.e., $I$ and $J$ are isometric. ∎

The following exercise gives one possible generalization of Proposition 6.7.

######  Problem 6.3.

Prove that if a metric space $X$ is compact, a metric space $Y$ is complete,
and $d_{GH}(X,Y)=0$, then $X$ is isometric to $Y$.

  * Solution.

By Theorem 2.24, it suffices to prove that $Y$ is a totally bounded space.
Choose an arbitrary $\varepsilon>0$. Since $d_{GH}(X,Y)=0$ then there exists
an admissible metric $d\in\mathcal{D}(X,Y)$ such that
$d_{H}(X,Y)<\varepsilon/3$. Since $X$ is compact, there exists a finite
$(\varepsilon/3)$-net $S\subset X$. Since $d_{H}(X,Y)<\varepsilon/3$, for each
$s\in S$ there exists $y_{s}\in Y$ for which $d(s,y_{s})<\varepsilon/3$, and
for each $y\in Y$ there exists $x\in X$ such that $|xy|<\varepsilon/3$. Since
$S$ is an $(\varepsilon/3)$-net in $X$, there exists $s\in S$ for which
$|xs|<\varepsilon/3$. Thus

$|yy_{s}|\leq|yx|+|xs|+d(s,y_{s})<\varepsilon,$

so the set $\\{y_{s}\\}_{s\in S}$ is a finite $\varepsilon$-net in $Y$.

######  Remark 6.8.

Even if both metric spaces $X$ and $Y$ are boundedly compact, Proposition 6.7
may not hold. To describe the corresponding example, we denote by $X$ and $Y$
the subsets of the Euclidean plane $\mathbb{R}^{2}$ constructed as follows.
Each of these spaces is obtained from the abscissa by adding vertical segments
between $(m,0)$ and $(m,\ell_{m})$, $m\in{\mathbb{Z}}$. In the case of $X$ we
put $\ell_{m}=|\sin m|$, and in the case of $Y$ let
$\ell_{m}=\bigl{|}\sin(m+1/2)\bigr{|}$. For the distances on $X$ and $Y$ we
take the corresponding internal metrics. Notice that the spaces $X$ and $Y$
can be considered as graphs whose points $(m,0)$ correspond to the vertices of
degree $3$, and the points $(m,\ell_{m})$ to the vertices of degree $1$.

It is easy to see that for any $\varepsilon>0$ there exists $n\in{\mathbb{N}}$
such that for all $m\in{\mathbb{Z}}$ it holds

$\Bigl{|}\bigl{|}\sin(m+n)\bigr{|}-\bigl{|}\sin(m+1/2)\bigr{|}\Bigr{|}<\varepsilon.$

Therefore, the subset $X$ can be shifted along the abscissa by the vector
$(n,0)$ in such a way that the resulting subset $X^{\prime}$, which is
isometric to $X$, satisfies $d_{H}(X^{\prime},Y)<\varepsilon$. Thus,
$d_{GH}(X,Y)=0$.

On the other hand, it is easy to see that the sets $\bigl{\\{}|\sin
m|\bigr{\\}}_{m\in{\mathbb{Z}}}$ and
$\Bigl{\\{}\bigl{|}\sin(m+1/2)\bigr{|}\Bigr{\\}}_{m\in{\mathbb{Z}}}$ do not
intersect. Suppose that $X$ and $Y$ are isometric, and $f\colon X\to Y$ is an
isometry. Since each isometry is a homeomorphism, then $f$ takes the vertices
of degree $1$ and $3$ to the vertices of the same degree, thus each segment in
$X$ between $(m,0)$ and $\bigl{(}m,|\sin m|\bigr{)}$ is mapped by $f$ onto a
segment of $Y$ between some $(n,0)$ and
$\bigl{(}n,|\sin(n+1/2)\bigr{|}\bigr{)}$. However, since $f$ is an isometry,
it has to preserve the lengths of these segments, a contradiction.

As follows from Theorem 6.4, the Gromov–Hausdorff distance between $X$ and $Y$
measures the least “discrepancy” for all possible “alignments” of these spaces
inside metric spaces constructed on $X\sqcup Y$. A natural question arises:
can all these alignments, perhaps for some special classes of metric spaces,
be realized inside the same ambient metric space? The following result answers
the question for the class of separable spaces.

Consider the metric space $\ell_{\infty}$ of all bounded sequences introduced
in Example 2.10. Recall that, by Theorem 2.26, each separable metric space is
isometrically embedded into $\ell_{\infty}$.

######  Proposition 6.9.

Let $X$ and $Y$ be separable metric spaces. Then

$d_{GH}(X,Y)=\inf d_{H}^{\ell_{\infty}}\bigl{(}\varphi(X),\psi(Y)\bigr{)},$

where the infimum is taken over all isometric embeddings $\varphi\colon
X\to\ell_{\infty}$ and $\psi\colon Y\to\ell_{\infty}$.

###### Proof.

The space $X\sqcup Y$ with an admissible metric $d\in\mathcal{D}(X,Y)$ is also
separable, therefore, by Theorem 2.26, it can be isometrically embedded into
$\ell_{\infty}$. ∎

For specific calculations of the Gromov–Hausdorff distance, other equivalent
definitions of this distance are useful.

Recall that _a relation_ between sets $X$ and $Y$ is a subset of the Cartesian
product $X\times Y$. Recall that $\mathcal{P}_{0}(X\times Y)$ denotes the set
of all nonempty subsets of $X\times Y$, i.e., the set of all nonempty
relations between $X$ and $Y$. Similarly to the case of mappings, for each
$\sigma\in\mathcal{P}_{0}(X\times Y)$ and for every $x\in X$ and $y\in Y$,
there are defined _the image_ $\sigma(x):=\bigl{\\{}y\in
Y:(x,y)\in\sigma\bigr{\\}}$ and _the preimage_ $\sigma^{-1}(y)=\bigl{\\{}x\in
X:(x,y)\in\sigma\bigr{\\}}$. Also, for $A\subset X$ and $B\subset Y$ their
_image_ and _preimage_ are defined as the union of the images and preimages of
their elements, respectively.

Let $\pi_{X}\colon X\times Y\to X$ and $\pi_{Y}\colon X\times Y\to Y$ be the
canonical projections $\pi_{X}(x,y)=x$ and $\pi_{Y}(x,y)=y$. We denote in the
same way the restrictions of these mappings to each relation $\sigma\subset
X\times Y$. A relation $R$ between $X$ and $Y$ is called _a correspondence_ if
the restrictions of the canonical projections $\pi_{X}$ and $\pi_{Y}$ to $R$
are surjective. In other words, for every $x\in X$ there exists $y\in Y$, and
for every $y\in Y$ there exists $x\in X$, such that $(x,y)\in R$. Thus, the
correspondence can be considered as a surjective multivalued mapping. The set
of all correspondences between $X$ and $Y$ is denoted by $\mathcal{R}(X,Y)$.

If $X$ and $Y$ are metric spaces, then for each relation
$\sigma\in\mathcal{P}_{0}(X\times Y)$ we define its _distortion
$\operatorname{dis}\sigma$_ as follows

$\operatorname{dis}\sigma=\sup\Bigl{\\{}\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}:(x,y),\,(x^{\prime},y^{\prime})\in\sigma\Bigr{\\}}.$

######  Problem 6.4.

Prove that for any $\sigma_{1},\sigma_{2}\in\mathcal{P}_{0}(X\times Y)$ such
that $\sigma_{1}\subset\sigma_{2}$, we have
$\operatorname{dis}\sigma_{1}\leq\operatorname{dis}\sigma_{2}$.

######  Problem 6.5.

Prove that for $R\in\mathcal{R}(X,Y)$ it holds $\operatorname{dis}R=0$ if and
only if $R$ is an isometry.

The next two constructions establish a link between correspondences from
$\mathcal{R}(X,Y)$ and admissible metrics on $X\sqcup Y$.

To start with, we consider an arbitrary admissible metric and use it to
construct a specific correspondence.

Let $\rho\in\mathcal{D}(X,Y)$ be an arbitrary admissible metric for metric
spaces $X$ and $Y$, and suppose that $\rho_{H}(X,Y)<\infty$. Choose arbitrary
$r\geq\rho_{H}(X,Y)$ for which the set $R^{\rho}_{r}=\\{(x,y):\rho(x,y)\leq
r\\}$ is a correspondence between $X$ and $Y$. Notice that we always can take
arbitrary $r>\rho_{H}(X,Y)$. Sometimes, for example, for compact $X$ and $Y$,
we can take $r=\rho_{H}(X,Y)$.

######  Proposition 6.10.

Under above notations, it holds $\operatorname{dis}R^{\rho}_{r}\leq 2r$.

###### Proof.

For any $(x,y),\,(x^{\prime},y^{\prime})\in R^{\rho}_{r}$ we have

$\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}=\bigl{|}\rho(x,x^{\prime})-\rho(y,y^{\prime})\bigr{|}\leq\rho(x,y)+\rho(x^{\prime},y^{\prime})\leq
2r.$

It remains to pass to supremum in definition of
$\operatorname{dis}R^{\rho}_{r}$. ∎

Now we start from a correspondence and construct a specific admissible metric.

Consider arbitrary correspondence $R\in\mathcal{R}(X,Y)$. Suppose that
$\operatorname{dis}R<\infty$. Extend the metrics of $X$ and $Y$ upto a
symmetric function $\rho^{R}$ defined on pairs of points from $X\sqcup Y$: for
$x\in X$ and $y\in Y$ put

$\rho^{R}(x,y)=\rho^{R}(y,x)=\inf\bigl{\\{}|xx^{\prime}|+|yy^{\prime}|+\frac{1}{2}\operatorname{dis}R:(x^{\prime},y^{\prime})\in
R\bigr{\\}}.$

######  Proposition 6.11.

Under above notations, let $\operatorname{dis}R>0$, then $\rho^{R}$ is an
admissible metric, and $\rho^{R}_{H}(X,Y)=\frac{1}{2}\operatorname{dis}R$.

###### Proof.

To simplify notation, we put $\rho:=\rho^{R}$.

Since $\operatorname{dis}R>0$ then $\rho$ is positively defined. Now we verify
the triangle inequality. It suffices to consider the case $x_{1},x_{2}\in X$,
$y\in Y$ and to prove the inequalities for the triangle $x_{1}x_{2}y$. Due to
symmetry reasons, we prove only two inequalities
$\rho(x_{1},y)+\rho(x_{2},y)\geq|x_{1}x_{2}|$ and
$\rho(x_{2},y)+|x_{1}x_{2}|\geq\rho(x_{1},y)$.

Let us start from the first one. Choose arbitrary
$(x_{1}^{\prime},y_{1}^{\prime}),\,(x_{2}^{\prime},y_{2}^{\prime})\in R$, then

$|x_{1}x_{1}^{\prime}|+|y_{1}^{\prime}y|+|x_{2}x_{2}^{\prime}|+|y_{2}^{\prime}y|+\operatorname{dis}R\geq|x_{1}x_{2}|-|x_{1}^{\prime}x_{2}^{\prime}|+|y_{1}^{\prime}y_{2}^{\prime}|+\operatorname{dis}R\geq|x_{1}x_{2}|,$

where the last inequality holds because
$|y_{1}^{\prime}y_{2}^{\prime}|-|x_{1}^{\prime}x_{2}^{\prime}|\geq-\operatorname{dis}R$
by definition. Thus,

$\rho(x_{1},y)+\rho(x_{2},y)=\inf\bigl{\\{}|x_{1}x_{1}^{\prime}|+|y_{1}^{\prime}y|+|x_{2}x_{2}^{\prime}|+|y_{2}^{\prime}y|+\operatorname{dis}R:(x_{1}^{\prime},y_{1}^{\prime}),\,(x_{2}^{\prime},y_{2}^{\prime})\in
R\bigr{\\}}\geq|x_{1}x_{2}|.$

Now we prove the second inequality. We have

$\rho(x_{2},y)+|x_{1}x_{2}|=\inf\bigl{\\{}|x_{2}x_{2}^{\prime}|+|y_{2}^{\prime}y|+\frac{1}{2}\operatorname{dis}R+|x_{1}x_{2}|:(x_{2}^{\prime},y_{2}^{\prime})\in
R\bigr{\\}}\geq\\\
\geq\inf\bigl{\\{}|x_{1}x_{2}^{\prime}|+|y_{2}^{\prime}y|+\frac{1}{2}\operatorname{dis}R:(x_{2}^{\prime},y_{2}^{\prime})\in
R\bigr{\\}}=\rho(x_{1},y).$

It remains to prove that $\rho_{H}(X,Y)=\frac{1}{2}\operatorname{dis}R$. Since
$R\in\mathcal{R}(X,Y)$ then for each $x\in X$ there exists $y\in Y$, and for
each $y\in Y$ there exists $x\in X$, such that $(x,y)\in R$ and, thus,
$\rho(x,y)=\frac{1}{2}\operatorname{dis}R$, therefore
$\rho_{H}(X,Y)\leq\frac{1}{2}\operatorname{dis}R$. Besides that, for any $x\in
X$ and $y\in Y$ it holds $\rho(x,y)\geq\frac{1}{2}\operatorname{dis}R$, thus
$\rho_{H}(X,Y)\geq\frac{1}{2}\operatorname{dis}R$, and the proof is complete.
∎

######  Theorem 6.12.

For any metric spaces $X$ and $Y$ we have

$d_{GH}(X,Y)=\frac{1}{2}\inf\bigl{\\{}\operatorname{dis}R:R\in\mathcal{R}(X,Y)\bigr{\\}}.$

###### Proof.

Denote by $I(X,Y)$ the right-hand side of the equality from the statement of
the theorem. We prove first that $d_{GH}(X,Y)\geq I(X,Y)$. If
$d_{GH}(X,Y)=\infty$, then the inequality holds.

Now, suppose that $d_{GH}(X,Y)<\infty$. Choose an arbitrary $r>d_{GH}(X,Y)$,
then, by Theorem 6.4, there exists $\rho\in\mathcal{D}(X,Y)$ for which
$\rho_{H}(X,Y)<r$. Consider the correspondence $R^{\rho}_{r}$ constructed
above. Then, by Proposition 6.10, we have $\operatorname{dis}R^{\rho}_{r}\leq
2r$, thus $I(X,Y)\leq r$. Since $r$ is arbitrary, we get $I(X,Y)\leq
d_{GH}(X,Y)$.

We now prove that $d_{GH}(X,Y)\leq I(X,Y)$. If $I(X,Y)=\infty$, then the
inequality holds.

Now, suppose that $I(X,Y)<\infty$. If there exists $R\in\mathcal{R}(X,Y)$ such
that $\operatorname{dis}R=0$, then, by Problem 6.5, we have $d_{GH}(X,Y)=0$,
and the equality holds. Now suppose that for all $R\in\mathcal{R}(X,Y)$ we
have $\operatorname{dis}R>0$. Choose an arbitrary $R\in\mathcal{R}(X,Y)$ such
that $\operatorname{dis}R<\infty$ and consider $\rho^{R}\in\mathcal{D}(X,Y)$
constructed above. By Proposition 6.11, we have
$\rho^{R}_{H}(X,Y)=\frac{1}{2}\operatorname{dis}R$, thus

$d_{GH}(X,Y)=\inf_{\rho\in\mathcal{D}(X,Y)}\rho_{H}(X,Y)\leq\inf\bigl{\\{}\rho^{R}_{H}(X,Y):R\in\mathcal{R}(X,Y),\,\operatorname{dis}R<\infty\bigr{\\}}=I(X,Y).$

∎

Recall that for a relation $\sigma$ between $X$ and $Y$, and a relation
$\theta$ between $Y$ and $Z$, _the composition $\theta\circ\sigma$_ is defined
by the following condition: $(x,z)\in\theta\circ\sigma$ if and only if there
exists $y\in Y$ such that $(x,y)\in\sigma$ and $(y,z)\in\theta$.

######  Problem 6.6.

Let $X$, $Y$, and $Z$ be metric spaces, $R_{1}\in\mathcal{R}(X,Y)$,
$R_{2}\in\mathcal{R}(Y,Z)$. Prove that

  1. (1)

$R_{2}\circ R_{1}\in\mathcal{R}(X,Z)$;

  2. (2)

$\operatorname{dis}(R_{2}\circ
R_{1})\leq\operatorname{dis}R_{1}+\operatorname{dis}R_{2}$;

  3. (3)

derive from the previous items the triangle inequality for the
Gromov–Hausdorff distance.

  * Solution.

(1) Let $x$ be an arbitrary point in $X$. Since $R_{1}$ is a correspondence,
there exists $y\in Y$ such that $(x,y)\in R_{1}$. Since $R_{2}$ is a
correspondence, there exists $z\in Y$ such that $(y,z)\in R_{2}$. Therefore,
$(x,z)\in R_{2}\circ R_{1}$. Similarly, for any $z\in Z$ there exists $x\in X$
such that $(x,z)\in R_{2}\circ R_{1}$. Thus, $R_{2}\circ R_{1}$ is a
correspondence.

(2) For any $(x,z),\,(x^{\prime},z^{\prime})\in R_{2}\circ R_{1}$ there exist
$y,\,y^{\prime}\in Y$ such that $(x,y),\,(x^{\prime},y^{\prime})\in R_{1}$ and
$(y,z),\,(y^{\prime},z^{\prime})\in R_{2}$, hence

$\bigl{|}|zz^{\prime}|-|xx^{\prime}|\bigr{|}=\bigl{|}|zz^{\prime}|-|yy^{\prime}|+|yy^{\prime}|-|xx^{\prime}|\bigr{|}\leq\bigl{|}|zz^{\prime}|-|yy^{\prime}|\bigr{|}+\bigl{|}|yy^{\prime}|-|xx^{\prime}|\bigr{|},$

and, passing to the suprema, we obtain what is required.

(3) Denote by $R(X,Y,Z)$ the subset of $R(X,Z)$ consisting of all
correspondences represented in the form $R_{2}\circ R_{1}$, where $R_{1}\in
R(X,Y)$ and $R_{2}\in R(Y,Z)$. Then, by Theorem 6.12 and the previous item, we
have

$d_{GH}(X,Z)=\frac{1}{2}\inf_{R\in\mathcal{R}(X,Z)}\operatorname{dis}R\leq\frac{1}{2}\inf_{R\in\mathcal{R}(X,Y,Z)}\operatorname{dis}R=\frac{1}{2}\mathop{\inf_{R_{1}\in\mathcal{R}(X,Y)}}_{R_{2}\in\mathcal{R}(Y,Z)}\operatorname{dis}(R_{2}\circ
R_{1})\leq\\\
\leq\frac{1}{2}\mathop{\inf_{R_{1}\in\mathcal{R}(X,Y)}}_{R_{2}\in\mathcal{R}(Y,Z)}(\operatorname{dis}R_{1}+\operatorname{dis}R_{2})\leq\frac{1}{2}\inf_{R_{1}\in\mathcal{R}(X,Y)}\operatorname{dis}R_{1}+\frac{1}{2}\inf_{R_{2}\in\mathcal{R}(Y,Z)}\operatorname{dis}R_{2}=d_{GH}(X,Y)+d_{GH}(Y,Z),$

as required.

We show one more approach to the study of the Gromov–Hausdorff distance.

######  Definition 6.13.

A mapping $f\colon X\to Y$ of metric spaces is called _an
$\varepsilon$-isometry_ if $\operatorname{dis}f<\varepsilon$ and $f(X)$ is an
$\varepsilon$-net in $Y$.

######  Theorem 6.14.

Let $X$ and $Y$ be arbitrary metric spaces and $\varepsilon>0$. Then

  1. (1)

if $d_{GH}(X,Y)<\varepsilon$ then there exists a $(2\varepsilon)$-isometry
$f\colon X\to Y$_;_

  2. (2)

if there exists an $\varepsilon$-isometry $f\colon X\to Y$ then it holds
$d_{GH}(X,Y)<2\varepsilon$.

###### Proof.

(1) By Theorem 6.12, there exists a relation $R\in\mathcal{R}(X,Y)$ such that
$\operatorname{dis}R<2\varepsilon$. For each $x\in X$ we choose an arbitrary
$y\in R(x)$ and put $f(x)=y$. Thus, we determined a mapping $f\colon X\to Y$,
and since $f\subset R$ (here we identify $f$ with its graph), by Problem 6.4
it holds $\operatorname{dis}f\leq\operatorname{dis}R<2\varepsilon$. Now we
choose an arbitrary $y^{\prime}\in Y$, an arbitrary $x\in R^{-1}(y^{\prime})$,
and let $y=f(x)$. Since
$\operatorname{diam}R(x)\leq\operatorname{dis}R<2\varepsilon$, it follows that
$|yy^{\prime}|<2\varepsilon$, therefore $f(X)$ is a $(2\varepsilon)$-net.

(2) Consider the relation $R=\bigl{\\{}(x,y):|f(x)y|<\varepsilon\bigr{\\}}$.
Since $f(X)$ is an $\varepsilon$-net, $R$ is a correspondence. To estimate the
distortion of $R$, we choose arbitrary $(x,y),(x^{\prime},y^{\prime})\in R$,
then

$\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}\leq\Bigl{|}|xx^{\prime}|-\bigl{|}f(x)f(x^{\prime})\bigr{|}\Bigr{|}+\Bigl{|}\bigl{|}f(x)f(x^{\prime})\bigr{|}-|yy^{\prime}|\Bigr{|}\leq\varepsilon+\bigl{|}f(x)y\bigr{|}+\bigl{|}y^{\prime}f(x^{\prime})\bigr{|}<3\varepsilon,$

therefore, $\operatorname{dis}R\leq 3\varepsilon<4\varepsilon$ and
$d_{GH}(X,Y)\leq\frac{1}{2}\operatorname{dis}R<2\varepsilon$. ∎

###  6.1 Irreducible correspondences

For arbitrary nonempty sets $X$ and $Y$, a correspondence
$R\in\mathcal{R}(X,Y)$ is called _irreducible_ if it is a minimal element of
the set $\mathcal{R}(X,Y)$ w.r.t. the order given by the inclusion relation.
The set of all irreducible correspondences between $X$ and $Y$ is denoted by
$\mathcal{R}^{0}(X,Y)$.

The following result is evident.

######  Proposition 6.15.

A correspondence $R\in\mathcal{R}(X,Y)$ is irreducible if and only if for any
$(x,y)\in R$ it holds

$\min\bigl{\\{}\\#R(x),\\#R^{-1}(y)\bigr{\\}}=1.$

######  Theorem 6.16.

Let $X$, $Y$ be arbitrary nonempty sets. Then for every $R\in\mathcal{R}(X,Y)$
there exists $R^{0}\in\mathcal{R}^{0}(X,Y)$ such that $R^{0}\subset R$. In
particular, $\mathcal{R}^{0}(X,Y)\neq\emptyset$.

######  Remark 6.17.

One could use the standard technique based on the Zorn lemma, but then we need
to guarantee that each chain $R_{1}\supset R_{2}\supset\cdots$ has a lower
bound, i.e., there exists a correspondence that belongs to all $R_{i}$.
However, this, generally speaking, is not true. As an example, consider
$X=Y={\mathbb{N}}$ and set $R_{k}=\bigl{\\{}(i,j):\max(i,j)\geq k\bigr{\\}}$.
It is clear that every $R_{k}$ belongs to $\mathcal{R}(X,Y)$, and that these
$R_{k}$ form a decreasing chain. However, $\cap R_{k}=\emptyset$, since for
any $i$ and $j$ there is $k$ for which $i<k$ and $j<k$, therefore
$(i,j)\not\in R_{k}$.

###### Proof of Theorem 6.16..

For each $x\in X$, choose an arbitrary $y\in R(x)$ and define a mapping
$f\colon X\to Y$ by setting $y=f(x)$. Let us note that $f\subset R$. Put
$Y_{1}=f(X)$ and $Y_{2}=Y\setminus Y_{1}$.

Now for each $y\in Y_{2}$ we choose an arbitrary $x\in R^{-1}(y)$ and define a
mapping $g\colon Y_{1}\to X$ by setting $x=g(y)$. In this case we have
$g^{-1}\subset R$. Put $X_{2}=g(Y_{2})$ and $X_{1}=X\setminus X_{2}$.

Let $Y_{3}=f(X_{2})$. It is clear that $Y_{3}\subset Y_{1}$.

Using $f$ and $g$, we define another relation: $h=f\cup g^{-1}$.

######  Lemma 6.18.

We have $h\in\mathcal{R}(X,Y)$.

###### Proof.

By the definition of $f$, for each $x\in X$ it holds
$\bigl{(}x,f(x)\bigr{)}\in f\subset h$.

Now consider an arbitrary $y\in Y$. If $y\in Y_{1}$, then, since
$Y_{1}=\operatorname{im}f$, there exists $x\in X$ such that $y=f(x)$,
therefore $(x,y)\in f\subset h$. If $y\in Y_{2}$, then, by the definition of
$g$, we have $\bigl{(}g(y),y\bigr{)}\in g^{-1}\subset h$. ∎

Now we define the relation $R^{0}$ by removing from $h$ some $(x,y)$ for each
$y\in Y_{3}$ according to the following rule:

  1. (1)

if $h^{-1}(y)\cap X_{1}\neq\emptyset$, then we remove $\bigl{(}h^{-1}(y)\cap
X_{2}\bigr{)}\times\\{y\\}$;

  2. (2)

if $h^{-1}(y)\cap X_{1}=\emptyset$, i.e., $h^{-1}(y)\subset X_{2}$, then we
remove all the elements from $h^{-1}(y)\times\\{y\\}$, except any one.

######  Lemma 6.19.

We have $R^{0}\in\mathcal{R}(X,Y)$.

###### Proof.

For every $y\in Y\setminus Y_{3}$ we remove nothing, therefore for such $y$
there always exists $x\in X$ such that $(x,y)\in R^{0}$.

Now let $y\in Y_{3}$. If $h^{-1}(y)\cap X_{1}\neq\emptyset$, then we do not
remove $(x,y)$ with $x\in h^{-1}(y)\cap X_{1}$, thus $(x,y)\in R^{0}$ for such
$x$. If $h^{-1}(y)\cap X_{1}=\emptyset$, then we do not remove some $x\in
h^{-1}(y)$, thus $(x,y)\in R^{0}$ for such $x$.

Now let us deal with $x\in X$. If $x\in X_{1}$, then we remove nothing,
therefore $(x,y)\in R^{0}$ for some $y\in Y$. If $x\in X_{2}$, then, since
$X_{2}=\operatorname{im}g$, there exists $y\in Y_{2}$ for which $x=g(y)$, but
we remove nothing for such $y$, thus $(x,y)\in R^{0}$. ∎

######  Lemma 6.20.

We have $R^{0}\in\mathcal{R}^{0}(X,Y)$.

###### Proof.

It is sufficient to show that for each pair $(x,y)\in R^{0}$ either $x$, or
$y$ do not belong to other pairs.

If $y\in Y_{2}$, then $y$ is included in the only pair
$\bigl{(}g(y),y\bigr{)}\in R^{0}$. If $y\in Y_{1}\setminus Y_{3}$, then
$y=f(x)$ for some $x\in X_{1}$, however such $x$ is included in the only pair
$\bigl{(}x,f(x)\bigr{)}\in R^{0}$.

Finally, now let $y\in Y_{3}$. If $h^{-1}(y)\cap X_{1}\neq\emptyset$, then we
removed all the pairs of the form $(x^{\prime},y)$, $x^{\prime}\in X_{2}$, so
$x\in X_{1}$, however, each such $x$ is included in exactly one pair, namely,
in $\bigl{(}x,f(x)\bigr{)}$. If $h^{-1}(y)\cap X_{1}=\emptyset$, then we
removed all the pairs $(x^{\prime},y)$, $x^{\prime}\in h^{-1}(y)\subset
X_{2}$, except some one, so $y$ is included in exactly one such pair. ∎

This lemma completes the proof of the theorem. ∎

Theorems 6.16 and 6.12, together with Problem 6.4, implies

######  Corollary 6.21.

For any metric spaces $X$ and $Y$ we have

$d_{GH}(X,Y)=\frac{1}{2}\inf\bigl{\\{}\operatorname{dis}R\mid
R\in\mathcal{R}^{0}(X,Y)\bigr{\\}}.$

Now we give another useful description of irreducible.

######  Proposition 6.22.

For any nonempty sets $X$, $Y$, and each $R\in\mathcal{R}^{0}(X,Y)$, there
exist and unique partitions $R_{X}=\\{X_{i}\\}_{i\in I}$ and
$R_{Y}=\\{Y_{i}\\}_{i\in I}$ of the sets $X$ and $Y$, respectively, such that
$R=\cup_{i\in I}X_{i}\times Y_{i}$. Moreover, $R_{X}=\cup_{y\in
Y}\bigl{\\{}R^{-1}(y)\bigr{\\}}$, $R_{Y}:=\cup_{x\in
X}\bigl{\\{}R(x)\bigr{\\}}$,

$\\{X_{i}\times Y_{i}\\}_{i\in I}=\cup_{(x,y)\in R}\\{R^{-1}(y)\times
R(x)\\},$

and for each $i$ it holds $\min\\{\\#X_{i},\\#Y_{i}\\}=1$.

Conversely, each set $R=\cup_{i\in I}X_{i}\times Y_{i}$, where
$\\{X_{i}\\}_{i\in I}$ and $\\{Y_{i}\\}_{i\in I}$ are partitions of nonempty
sets $X$ and $Y$, respectively, such that for each $i$ it holds
$\min\\{\\#X_{i},\\#Y_{i}\\}=1$, is an irreducible correspondence between $X$
and $Y$.

###### Proof.

First, let $R\in\mathcal{R}^{0}(X,Y)$. Put $R_{X}=\cup_{y\in
Y}\bigl{\\{}R^{-1}(y)\bigr{\\}}$, $R_{Y}=\cup_{x\in
X}\bigl{\\{}R(x)\bigr{\\}}$, and show that $R_{X}$ and $R_{Y}$ are partitions.
We show it for $R_{Y}$ (for $R_{X}$ the proof is the same).

Notice first that $R_{X}$ and $R_{Y}$ are covers because $R$ is a
correspondence. Now, suppose to the contrary that $R_{Y}$ is not a partition,
i.e., there exist two different elements of $R_{Y}$, say $R(x)$ and
$R(x^{\prime})$, such that $R(x)\cap R(x^{\prime})\neq\emptyset$. Since
$R(x)\neq R(x^{\prime})$, one of them, say $R(x)$, contains two different
elements $y$ and $y^{\prime}$, such that one of them, say $y$, belongs to
$R(x)\cap R(x^{\prime})$. This means that for the pair $(x,y)$ it holds
$\\#R(x)\geq 2$ and $R^{-1}(y)\geq 2$, a contradiction to Proposition 6.15.

Now, we put $R_{X}=\\{X_{i}\\}_{i\in I}$. Note that for any $x,x^{\prime}\in
X_{i}$ we have $R(x)=R(x^{\prime})$. Indeed, by definition, $X_{i}=R^{-1}(y)$
for some $y\in Y$, thus $R(x)\cap R(x^{\prime})\neq\emptyset$ and, therefore,
$R(x)=R(x^{\prime})$ because $R_{Y}$ is a partition.

Choose arbitrary $i\in I$, $x\in X_{i}$, and put $Y_{i}=R(x)$. Then, this
definition is correct (does not depend on the choice of $x$). We show that the
mapping $\varphi\colon X_{i}\mapsto Y_{i}$ is a bijection between $R_{X}$ and
$R_{Y}$.

If $\varphi$ is not injective, then there exist $x,x^{\prime}\in X$ lying in
different elements of the partition $R_{X}$ for which $R(x)=R(x^{\prime})$.
Thus $x,x^{\prime}\in R^{-1}(y)\in R_{X}$ for $y\in R(x)$, a contradiction.

Finally, $\varphi$ is surjective, since for any $Y_{i}$, $y\in Y_{i}$, the set
$R^{-1}(y)$ is an element of the partition $R_{X}$. Choose an arbitrary $x\in
R^{-1}(y)$, then $R(x)\in R_{Y}$ contains $y$, therefore
$\varphi\bigl{(}R^{-1}(y)\bigr{)}=Y_{i}$.

Since for any $x,x^{\prime}\in X_{i}$ we have $R(x)=R(x^{\prime})=Y_{i}$, then
$X_{i}\times Y_{i}\subset R$. On the other hand, since $R_{X}$ is a partition
of $X$, for any $x\in X$ there exists $X_{i}\in R_{X}$ such that $x\in X_{i}$,
therefore each $(x,y)\in R$ is contained in some $X_{i}\times Y_{i}$.

To prove the equality $\min\\{\\#X_{i},\\#Y_{i}\\}=1$, let us note that for
any $(x,y)\in R$, $x\in X_{i}$, and $y\in Y_{i}$, we have $X_{i}=R^{-1}(y)$
and $Y_{i}=R(x)$, thus, $\\{X_{i}\times Y_{i}\\}_{i\in I}=\cup_{(x,y)\in
R}\\{R^{-1}(y)\times R(x)\\}$. It suffices to apply Proposition 6.15.

The uniqueness of the partitions is the standard fact from the set theory.

The converse is trivial. ∎

Let $X$ be an arbitrary set different from singleton, and $m$ a cardinal
number, $2\leq m\leq\\#X$. By $\mathcal{D}_{m}(X)$ we denote the family of all
possible partitions of the set $X$ into $m$ nonempty subsets.

Now let $X$ be a metric space. Then for each $D=\\{X_{i}\\}_{i\in
I}\in\mathcal{D}_{m}(X)$ we put

$\operatorname{diam}D=\sup_{i\in I}\operatorname{diam}X_{i}.$

Further, for any nonempty $A,B\subset X$, we have already defined $|AB|$ as
$\inf\bigl{\\{}|ab|:(a,b)\in A\times B\bigr{\\}}$. We also need
$|AB|^{\prime}:=\sup\bigl{\\{}|ab|:(a,b)\in A\times B\bigr{\\}}$. Further, for
each $D=\\{X_{i}\\}_{i\in I}\in\mathcal{D}_{m}(X)$ we put

$\alpha(D)=\inf\bigl{\\{}|X_{i}X_{j}|:i\neq
j\bigr{\\}}\quad\text{and}\quad\beta(D)=\sup\bigl{\\{}|X_{i}X_{j}|^{\prime}:i\neq
j\bigr{\\}}.$

Also notice that $|X_{i}X_{i}|=0$,
$|X_{i}X_{i}|^{\prime}=\operatorname{diam}X_{i}$ and hence
$\operatorname{diam}D=\sup_{i\in I}|X_{i}X_{i}|^{\prime}$.

The next result follows easily from the definition of distortion, as well as
from Proposition 6.22.

######  Proposition 6.23.

Let $X$ and $Y$ be arbitrary metric spaces, $D_{X}=\\{X_{i}\\}_{i\in I}$,
$D_{Y}=\\{Y_{i}\\}_{i\in I}$, $\\#I\geq 2$, be some partitions of the spaces
$X$ and $Y$, respectively, and $R=\cup_{i\in I}X_{i}\times
Y_{i}\in\mathcal{R}(X,Y)$. Then

$\operatorname{dis}R=\sup\bigl{\\{}|X_{i}X_{j}|^{\prime}-|Y_{i}Y_{j}|,\,|Y_{i}Y_{j}|^{\prime}-|X_{i}X_{j}|:i,j\in
I\bigr{\\}}=\\\
=\sup\bigl{\\{}\operatorname{diam}D_{X},\,\operatorname{diam}D_{Y},\,|X_{i}X_{j}|^{\prime}-|Y_{i}Y_{j}|,\,|Y_{i}Y_{j}|^{\prime}-|X_{i}X_{j}|:i,j\in
I,\,i\neq j\bigr{\\}}\leq\\\
\leq\max\bigl{\\{}\operatorname{diam}D_{X},\operatorname{diam}D_{Y},\beta(D_{X})-\alpha(D_{Y}),\beta(D_{Y})-\alpha(D_{X})\bigr{\\}}.$

In particular, if $R\in\mathcal{R}^{0}(X,Y)$, then in the previous formula we
can take $R_{X}$ and $R_{Y}$ defined in Proposition 6.22 for $D_{X}$ and
$D_{Y}$, respectively.

It will also be convenient for us to represent a relation
$\sigma\in\mathcal{P}_{0}(X\times Y)$ as a bipartite graph. Then the degree
$\deg$ of each vertex is defined: $\deg_{\sigma}(x)=\\#\sigma(x)$ and
$\deg_{\sigma}(y)=\\#\sigma^{-1}(y)$ .

######  Problem 6.7.

Let $R\in\mathcal{R}^{0}(X,Y)$, $x\in X$, $\deg_{R}(x)>1$. Prove that for each
$x^{\prime}\in X$, $x^{\prime}\neq x$, it holds $R(x)\cap
R(x^{\prime})=\emptyset$.

Problem 6.7 immediately implies

######  Corollary 6.24.

Let $\\#X\geq 2$ and $\\#Y\geq 2$, then for any $R\in\mathcal{R}^{0}(X,Y)$
there is no $x\in X$ such that $\\{x\\}\times Y\subset R$.

######  Example 6.25.

Let $X=\\{x_{1},x_{2}\\}$ and $Y=\\{y_{1},y_{2}\\}$, then, by Corollary 6.24,
the set $\mathcal{R}^{0}(X,Y)$ consists only of bijections, therefore

$2d_{GH}(X,Y)=\bigl{|}|x_{1}x_{2}|-|y_{1}y_{2}|\bigr{|}.$

_Thus, the set of isometric classes of two-point metric spaces endowed with
the Gromov–Hausdorff distance is a metric space isometric to the open ray
$x>0$ of the real line $\mathbb{R}$ with coordinate $x$_.

######  Example 6.26.

Consider two three-point metric spaces $X=\\{x_{1},x_{2},x_{3}\\}$ and
$Y=\\{y_{1},y_{2},y_{3}\\}$. Put $\rho_{ij}=|x_{i}x_{j}|=:\rho_{k}$ and
$\nu_{ij}=|y_{i}y_{j}|=:\nu_{k}$, where $\\{i,j,k\\}=\\{1,2,3\\}$. Without
loss of generality, we assume that $\rho_{1}\leq\rho_{2}\leq\rho_{3}$ and
$\nu_{1}\leq\nu_{2}\leq\nu_{3}$. We will show that

$d_{GH}(X,Y)=\frac{1}{2}\max\bigl{\\{}|\rho_{1}-\nu_{1}|,|\rho_{2}-\nu_{2}|,|\rho_{3}-\nu_{3}|\bigr{\\}}.$

By Corollary 6.21, it suffices to describe all irreducible correspondences
$R_{m}\in\mathcal{R}^{0}(X,Y)$. We will use Proposition 6.22. There are three
types of partitions of a three-point space: (1) into one-point subsets, (2)
into one two-point subset and one-point subset, and (3) into one three-point
subset. By Proposition 6.22, an irreducible correspondence defines a bijection
between partitions, therefore both spaces have to be partitioned in the same
way. Case (3) is not realized by Corollary 6.24, in case (1) we have a
bijection, and in case (2) one-point and two-point subsets have to correspond
to each other. Thus, we have two types of correspondences: if
$\\{i,j,k\\}=\\{p,q,r\\}=\\{1,2,3\\}$, then

  1. (1)

$R_{1}=\bigl{\\{}(x_{i},y_{p}),(x_{j},y_{q}),(x_{k},y_{r})\bigr{\\}}$,

  2. (2)

$R_{2}=\bigl{\\{}(x_{i},y_{q}),(x_{i},y_{r}),(x_{j},y_{p}),(x_{k},y_{p})\bigr{\\}}$.

We have

$\displaystyle\operatorname{dis}R_{1}=\max\bigl{\\{}|\rho_{ij}-\nu_{pq}|,|\rho_{ik}-\nu_{pr}|,|\rho_{jk}-\nu_{qr}|\bigr{\\}},$
$\displaystyle\operatorname{dis}R_{2}=\max\bigl{\\{}|\rho_{ij}-\nu_{pq}|,|\rho_{ik}-\nu_{pr}|,\rho_{jk},\nu_{qr},|\rho_{ij}-\nu_{pr}|,|\rho_{ik}-\nu_{pq}|\bigr{\\}}.$

Note that $\max\\{\rho_{jk},\nu_{qr}\\}\geq|\rho_{jk}-\nu_{qr}|$, therefore
$\operatorname{dis}R_{2}\geq\operatorname{dis}R_{1}$, so it is enough to
consider only the bijections $R_{1}$.

We also note that each bijection $R_{1}$ defines a bijection between the sets
$\\{\rho_{a}\\}$ and $\\{\nu_{a}\\}$. We show that the bijection
$\cup_{i=1}^{3}\bigl{\\{}(\rho_{i},\nu_{i})\bigr{\\}}$ is optimal, i.e., if we
replace this bijection with any other bijection $\psi$, we cannot get a lower
value than $M=\max_{i}|\rho_{i}-\nu_{i}|$. Put
$M^{\prime}=\max_{i}\bigl{|}\rho_{i}-\psi(\rho_{i})\bigr{|}$. We need to show
that $M^{\prime}\geq M$.

Let $M=|\rho_{1}-\nu_{1}|$, and suppose, without loss of generality, that
$\rho_{1}\leq\nu_{1}$, thus $M=\nu_{1}-\rho_{1}$. Since
$\psi(\rho_{1})\geq\nu_{1}$, then $M^{\prime}\geq\psi(\rho_{1})-\rho_{1}\geq
M$. Similarly we deal with the case $M=|\rho_{3}-\nu_{3}|$.

Now, let $M=|\rho_{2}-\nu_{2}|$, and $\rho_{2}\leq\nu_{2}$, i.e.,
$M=\nu_{2}-\rho_{2}$. If $\psi(\rho_{2})\neq\nu_{1}$, them $M^{\prime}\geq M$.
Suppose now that $\psi(\rho_{2})=\nu_{1}$, then $\psi(\rho_{1})$ equal either
$\nu_{2}$, or $\nu_{3}$. Thus
$M^{\prime}\geq\psi(\rho_{1})-\rho_{1}\geq\nu_{2}-\rho_{1}\geq\nu_{2}-\rho_{2}=M$.

Thus, the set of isometry classes of three-point metric spaces endowed with
the Gromov–Hausdorff distance is a metric space isometric to the polyhedral
cone

$\bigl{\\{}(x,y,z):0<x\leq y\leq z\leq x+y\bigr{\\}}$

in the space $\mathbb{R}^{3}_{\infty}$, where the latter denotes the space
$\mathbb{R}^{3}$ with the metric generated by the norm
$\bigl{\|}(x,y,z)\bigr{\|}_{\infty}=\max\bigl{\\{}|x|,|y|,|z|\bigr{\\}}$. The
isometry is given by the formula

$\\{x_{1},x_{2},x_{3}\\}\mapsto\frac{1}{2}(\rho_{1},\rho_{2},\rho_{3}).$

###  6.2 A few more examples

The following statement immediately follows from the definition of the
Gromov–Hausdorff distance and Item (4) of Problem 5.1.

######  Example 6.27.

Let $Y$ be an arbitrary $\varepsilon$-net of a metric space $X$. Then
$d_{GH}(X,Y)\leq d_{H}(X,Y)\leq\varepsilon$. Thus, every compact metric space
is approximated (according to the Gromov-Hausdorff metric) with any accuracy
by finite metric spaces.

######  Example 6.28.

Denote by $\Delta_{1}$ a one-point metric space. Then for any metric space $X$
we have

$d_{GH}(\Delta_{1},X)=\frac{1}{2}\operatorname{diam}X.$

Indeed, $\mathcal{R}(\Delta_{1},X)$ consists of exactly one correspondence
$R$, namely, of $R=\Delta_{1}\times X$, thus,
$\operatorname{dis}R=\operatorname{diam}X$, and it remains to use Theorem
6.12.

######  Example 6.29.

Let $X$ and $Y$ be some metric spaces, and the diameter of one of them is
finite. Then

$d_{GH}(X,Y)\geq\frac{1}{2}|\operatorname{diam}X-\operatorname{diam}Y|.$

Indeed, if $\operatorname{diam}X<\infty$ and $\operatorname{diam}Y=\infty$,
then for any $\rho\in\mathcal{D}(X,Y)$ we have $\rho_{H}(X,Y)=\infty$,
otherwise $Y\subset U_{r}(X)$ for some finite $r$ and, therefore,
$\operatorname{diam}Y<\infty$.

Now let the both $\operatorname{diam}X$ and $\operatorname{diam}Y$ are finite.
Then it suffices to use the triangle inequality (Proposition 6.6) for the
triple $X$, $Y$, $\Delta_{1}$, and Example 6.28.

######  Example 6.30.

Let $X$ and $Y$ be some metric spaces, then

$d_{GH}(X,Y)\leq\frac{1}{2}\max\\{\operatorname{diam}X,\operatorname{diam}Y\\},$

in particular, if $X$ and $Y$ are bounded metric spaces, then
$d_{GH}(X,Y)<\infty$.

Indeed, if the diameter of one of the spaces $X$, $Y$ is infinite, then the
inequality holds. If both spaces are singletons, then everything is also
obvious. Now let
$0<d:=\max\\{\operatorname{diam}X,\operatorname{diam}Y\\}<\infty$. Then for
$R=X\times Y\in\mathcal{R}(X,Y)$ we have $\operatorname{dis}R=d$, thus, by
Proposition 6.11, it holds
$\rho^{R}_{H}(X,Y)=\frac{1}{2}\operatorname{dis}R=d/2$, therefore,
$d_{GH}(X,Y)\leq d/2$.

Recall that for an arbitrary metric space $X$ and a real number $\lambda>0$,
by $\lambda X$ we denote the metric space obtained from $X$ by multiplying all
distances by $\lambda$. For $\lambda=0$ we set $\lambda X=\Delta_{1}$.

######  Example 6.31.

For any bounded metric space $X$ and any $\lambda\geq 0$, $\mu\geq 0$, we have
$d_{GH}(\lambda X,\mu X)=\frac{1}{2}|\lambda-\mu|\operatorname{diam}X$, in
particularly, for any $0\leq a<b$ the curve $\gamma(t):=t\,X$, $t\in[a,b]$, is
shortest.

Indeed, for the identity correspondence $R\in\mathcal{R}(\lambda X,\mu X)$ we
have $\operatorname{dis}R=|\lambda-\mu|\operatorname{diam}X$, hence
$d_{GH}(\lambda X,\mu X)\leq\frac{1}{2}|\lambda-\mu|\operatorname{diam}X$ by
Theorem 6.12. On the other hand, by Example 6.29 we have

$d_{GH}(\lambda X,\mu X)\geq\frac{1}{2}\bigl{|}\operatorname{diam}(\lambda
X)-\operatorname{diam}(\mu
X)\bigr{|}=\frac{1}{2}|\lambda-\mu|\operatorname{diam}X.$

It remains to note that

$|\gamma|=\sup_{a=t_{0}<\cdots<t_{n}=b}\sum_{i=1}^{n}d_{GH}(t_{i-1}\,X,\,t_{i}\,X)=\frac{1}{2}(b-a)\operatorname{diam}X=d_{GH}(a\,X,\,b\,X),$

hence $\gamma$ is shortest.

######  Example 6.32.

Let $X$ and $Y$ be metric spaces, then for any $\lambda>0$ we have
$d_{GH}(\lambda X,\lambda Y)=\lambda\,d_{GH}(X,Y)$. If, in addition,
$d_{GH}(X,Y)<\infty$, then the equality holds for all $\lambda\geq 0$.

Indeed, let $\lambda>0$. Then for each correspondence $R\in\mathcal{R}(X,Y)$
and the correspondence $R_{\lambda}\in\mathcal{R}(\lambda X,\lambda Y)$, which
coincides with $R$ as a set, we have
$\operatorname{dis}R_{\lambda}=\lambda\operatorname{dis}R$. It remains to use
Theorem 6.12. We now verify that under the condition $d_{GH}(X,Y)<\infty$ the
equality holds for $\lambda=0$ as well. With this $\lambda$, we have $\lambda
X=\lambda Y=\Delta_{1}$, therefore $d_{GH}(\lambda X,\lambda Y)=0$. Since
$d_{GH}(X,Y)<\infty$, the value $\lambda\,d_{GH}(X,Y)$ vanishes too.

###  6.3 $\operatorname{GH}$-convergence and $\operatorname{GH}$-limits

For a sequence $X_{k}$ of metric spaces that converges w.r.t. the
Gromov–Hausdorff distance to a metric space $X$, we say for short that the
sequence _$\operatorname{GH}$ -converges_ and write this as
$X_{k}\xrightarrow{\operatorname{GH}}X$. We call $X$ _the
$\operatorname{GH}$-limit_ and denote it by $\operatorname{GH-
lim}_{k\to\infty}X_{k}$.

Let us present a few simple observations.

  1. (1)

Let $X=\operatorname{GH-lim}_{k\to\infty}X_{k}$, $Y=\operatorname{GH-
lim}_{k\to\infty}X_{k}$, one of $X$ and $Y$ be compact, and the other one be
complete, then $X$ and $Y$ are isometric. Indeed, due to the triangle
inequality, we have $d_{GH}(X,Y)=0$. It remains to use Problem 6.3.

  2. (2)

Hausdorff convergence implies $\operatorname{GH}$-convergence.

  3. (3)

Each compact metric space is a $\operatorname{GH}$-limit of finite metric
spaces (of its finite $1/k$-nets).

######  Theorem 6.33.

Let $X_{k}\xrightarrow{\operatorname{GH}}Y$. If all $X_{k}$, starting from
some $k$, have one of the properties listed below, then this property is
inherited by the space $Y$_:_

  1. (1)

the diameter equals infinity _;_

  2. (2)

the diameter is bounded by a certain number $D$ _(_ in fact,
$\operatorname{diam}X_{k}\to\operatorname{diam}Y$_)__;_

  3. (3)

separability _;_

  4. (4)

total boundedness _;_

  5. (5)

if $Y$ is complete, then bounded compactness _;_

  6. (6)

if $Y$ is complete, then the intrinsicness.

###### Proof.

Without loss of generality, we assume that each of there properties holds for
all $k$, and that $d_{GH}(X_{k},Y)<1/k$. By Theorem 6.12, for each
$k\in{\mathbb{N}}$ there exists $R_{k}\in\mathcal{R}(X_{k},Y)$ such that
$\operatorname{dis}R_{k}<2/k$. In addition, by Theorem 6.14, for each
$k\in{\mathbb{N}}$ there exist $(2/k)$-isometries $f_{k}\colon X_{k}\to Y$ and
$g_{k}\colon Y\to X_{k}$.

(1) If $\operatorname{diam}Y<\infty$, then, by Example 6.29, we have
$d_{GH}(X_{k},Y)=\infty$, a contradiction.

(2) Since $g_{k}$ is $(2/k)$-isometry, then $\operatorname{dis}g_{k}<2/k$ and,
hence, for any $y,y^{\prime}\in Y$ we have
$\Bigl{|}|yy^{\prime}|-\bigl{|}g_{k}(y)g_{k}(y^{\prime})\bigr{|}\Bigr{|}<2/k$,
thus

$|yy^{\prime}|<\bigl{|}g_{k}(y)g_{k}(y^{\prime})\bigr{|}+2/k\leq\operatorname{diam}X_{k}+2/k.$

Since $y,y^{\prime}\in Y$ are arbitrary, we get
$\operatorname{diam}Y\leq\operatorname{diam}X_{k}+2/k$. Swapping $g_{k}$ and
$f_{k}$, we get $\operatorname{diam}X_{k}\leq\operatorname{diam}Y+2/k$, i.e.,
$|\operatorname{diam}X_{k}-\operatorname{diam}Y|<2/k$, therefore,
$\operatorname{diam}X_{k}\to\operatorname{diam}Y$ and, thus,
$\operatorname{diam}Y\leq D$.

(3) In each $X_{k}$ we choose a countable everywhere dense subset $S_{k}$.
Since $f_{k}$ is $(2/k)$-isometry, for any $y\in Y$ there exists $x_{k}\in
X_{k}$ such that $\bigl{|}yf_{k}(x_{k})\bigr{|}<2/k$. Since $S_{k}$ is
everywhere dense in $X_{k}$, there exists $s_{k}\in S_{k}$ such that
$|x_{k}s_{k}|<1/k$. Now the condition $\operatorname{dis}f_{k}<2/k$ implies
that $|f_{k}(s_{k})f_{k}(x_{k})|<3/k$, therefore,
$\bigl{|}f_{k}(s_{k})y\bigr{|}<5/k$, and hence $f_{k}(S_{k})$ is a countable
$(5/k)$-net in $Y$. It remains to note that $\cup_{k=1}^{\infty}f_{k}(S_{k})$
is a countable everywhere dense subset of $Y$.

(4) In each $X_{k}$ we choose a finite $(1/k)$-net $S_{k}$. Repeating word-by-
word the reasoning from Item (3), we obtain that $f_{k}(S_{k})$ is a finite
$(5/k)$-net. Since $k$ is arbitrary, we get what is required.

(5) Choose an arbitrary closed bounded $Z\subset Y$. We have to show that it
is compact. Since $\operatorname{dis}f_{k}<2/k$, then $f_{k}^{-1}(Z)$ is
bounded. Let $W$ be the closure of $f_{k}^{-1}(Z)$, then $W$ is compact, in
particular, it contains a finite $(1/k)$-net $S_{k}$. As was discussed above,
$f_{k}(S_{k})$ is a finite $(3/k)$-net in $f(W)\supset Z$ and, thus, there
exists a finite $(6/k)$-net $Z_{k}$ in $Z$. Since $k$ is arbitrary, we get
that $Z$ is totally bounded. Since $Z$ is closed, it is compact.

(6) By Theorem 3.51, it suffices to show that for any $y,y^{\prime}\in Y$ and
any $\varepsilon>0$ there exists an $\varepsilon$-midpoint between $y$ and
$y^{\prime}$. Choose $k$ such that $4/k<\varepsilon$, and arbitrary $x_{k}\in
R_{k}^{-1}(y)$, $x^{\prime}_{k}\in R_{k}^{-1}(y^{\prime})$. Since $X_{k}$ is
intrinsic, there exists a $(1/k)$-midpoint $s$ between $x_{k}$ and
$x^{\prime}_{k}$. Choose arbitrary $w\in R_{k}(s)$. Since $s$ is
$(1/k)$-midpoint, and $\operatorname{dis}R_{k}<2/k$, we have
$\bigl{|}|x_{k}s|-|x_{k}x^{\prime}_{k}|/2\bigr{|}<1/k$,
$\bigl{|}|x^{\prime}_{k}s|-|x_{k}x^{\prime}_{k}|/2\bigr{|}<1/k$,
$\bigl{|}|x_{k}s|-|yw|\bigr{|}<2/k$,
$\bigl{|}|x^{\prime}_{k}s|-|y^{\prime}w|\bigr{|}<2/k$,
$\bigl{|}|x_{k}x^{\prime}_{k}|-|yy|\bigr{|}<2/k$, thus
$\bigl{|}|yw|-|yy^{\prime}|/2\bigr{|}<4/k<\varepsilon$ and
$\bigl{|}|y^{\prime}w|-|yy^{\prime}|/2\bigr{|}<4/k<\varepsilon$, what is
required. ∎

######  Corollary 6.34.

Let $X_{k}\xrightarrow{\operatorname{GH}}Y$, all $X_{k}$ are boundedly compact
and intrinsic _(_ such $X_{k}$ are strictly intrinsic by Corollary 3.45 _)_ ,
$Y$ is complete. Then $Y$ is strictly intrinsic. Moreover, if we abandon the
bounded compactness property, then $Y$ may be not strictly intrinsic, namely,
the GH-limit of strictly intrinsic metric spaces may be not strictly
intrinsic.

###### Proof.

By Item (5) and Item (6) of Theorem6.33, the space $Y$ is boundedly compact
and intrinsic. It remains to apply Corollary 3.45.

To verify the second statement of the corollary, let us consider a metric
graph $Y$ obtained by gluing the ends of the segments $[0,1+1/n]$,
$n\in{\mathbb{N}}$ (all $0$ are glued together, and all ends $1+1/n$ are also
glued together). Then $Y$ is complete, intrinsic, but not strictly intrinsic.
For $X_{k}$ we take the space obtained from $Y$ by replacing the segment
$[0,1+1/k]$ with the segment $[0,1]$. Then all $X_{k}$ are complete and
strictly intrinsic, however, all they are not boundedly compact. ∎

######  Problem 6.8.

Let $X=\\{x^{1},\ldots,x^{n}\\}$ be a finite metric space. Prove that a
sequence $X_{k}$ of metric spaces $\operatorname{GH}$-converges to $X$ if and
only if for sufficiently large $k$ there exist partitions
$\\{X_{k}^{i}\\}_{i=1}^{n}\in\mathcal{D}_{n}(X_{k})$ such that
$|X_{k}^{i}X_{k}^{j}|\to|x^{i}x^{j}|$ for any $1\leq i,\,j\leq n$.

Let $d_{k}$ be a sequence of metrics on a nonempty set $X$. We say that the
metric spaces $X_{k}=(X,d_{k})$ _uniformly converges_ to a metric space
$Y=(X,d)$ if the functions $d_{k}$ uniformly converges to $d$, i.e., if

$\sup_{x,x^{\prime}\in
X}\bigl{|}d_{k}(x,x^{\prime})-d(x,x^{\prime})\bigr{|}\to 0.$

######  Problem 6.9 (Uniform convergence).

Prove that if metric spaces $X_{k}$ uniformly converges to a metric space $Y$
then $X_{k}\xrightarrow{\operatorname{GH}}Y$.

Recall that for any Lipschitz mapping $f\colon X\to Y$ of metric spaces we
defined the dilatation $\operatorname{dil}f$ as the minimal Lipschitz constant
for $f$, see Section 2.2. Also, we defined _bi-Lipschitz mapping_ between
metric spaces as a bijective mapping such that it and its inverse as Lipschitz
ones. Now we define _the Lipschitz distance $d_{L}$_ between metric spaces $X$
and $Y$ as the following value:

$d_{L}(X,Y)=\inf_{f\colon X\to
Y}\log\bigl{(}\max\\{\operatorname{dil}f,\,\operatorname{dil}f^{-1}\\}\bigr{)},$

where infimum is taken over all bi-Lipschitz mappings (if there is no such
mappings then $d_{L}(X,Y)=\infty$).

######  Problem 6.10 (Lipschitz convergence).

Prove that if metric spaces $X_{k}$ converges to a bounded metric space $Y$
w.r.t. the Lipschitz distance, then $X_{k}\xrightarrow{\operatorname{GH}}Y$.
Does it remain true without the boundedness assumption?

######  Problem 6.11.

Let the metric space $X_{k}$ be obtained from the standard sphere
$S^{2}\subset\mathbb{R}^{3}$ by removing a ball of radius $1/k$. Prove that
$X_{k}\xrightarrow{\operatorname{GH}}S^{2}$. Prove that if we change $S^{2}$
to the circle $S^{1}$, then the similar statement does not hold. In the both
cases we consider the interior metrics.

## References to Chapter 6

  * [1] Burago D., Burago Yu., Ivanov S. _A Course in Metric Geometry_. Graduate Studies in Mathematics, vol.33, A.M.S., Providence, RI, 2001.
  * [2] Ghanaat P. “Gromov-Hausdorff distance and applications”. In: Summer school “Metric Geometry”, Les Diablerets, August 25–30, 2013, https://math.cuso.ch/fileadmin/math/document/gromov-hausdorff.pdf

### Exercises to Chapter 6

######  Exercise 6.1.

Prove that for any metric spaces $X$ and $Y$ there exists a realization of
$(X,Y)$.

######  Exercise 6.2.

Prove that for any metric spaces $X$ and $Y$ there exists at least one
admissible metric, i.e., the set $\mathcal{D}(X,Y)$ is not empty.

######  Exercise 6.3.

Prove that for arbitrary metric spaces $X$ and $Y$, any
$\sigma_{1},\sigma_{2}\in\mathcal{P}_{0}(X\times Y)$ such that
$\sigma_{1}\subset\sigma_{2}$, we have
$\operatorname{dis}\sigma_{1}\leq\operatorname{dis}\sigma_{2}$.

######  Exercise 6.4.

Prove that for arbitrary metric spaces $X$ and $Y$, any $R\in\mathcal{R}(X,Y)$
it holds $\operatorname{dis}R=0$ if and only if $R$ is an isometry.

######  Exercise 6.5.

Let $X$ and $Y$ be arbitrary sets, $R\in\mathcal{R}^{0}(X,Y)$, $x\in X$,
$\deg_{R}(x)>1$. Prove that for each $x^{\prime}\in X$, $x^{\prime}\neq x$, it
holds $R(x)\cap R(x^{\prime})=\emptyset$.

######  Exercise 6.6.

Let $X=\\{x^{1},\ldots,x^{n}\\}$ be a finite metric space. Prove that a
sequence $X_{k}$ of metric spaces $\operatorname{GH}$-converges to $X$ if and
only if for sufficiently large $k$ there exist partitions
$\\{X_{k}^{i}\\}_{i=1}^{n}\in\mathcal{D}_{n}(X_{k})$ such that
$|X_{k}^{i}X_{k}^{j}|\to|x^{i}x^{j}|$ for any $1\leq i,\,j\leq n$.

######  Exercise 6.7 (Uniform convergence).

Prove that if metric spaces $X_{k}$ uniformly converges to a metric space $Y$
then $X_{k}\xrightarrow{\operatorname{GH}}Y$.

######  Exercise 6.8 (Lipschitz convergence).

Prove that if metric spaces $X_{k}$ converges to a bounded metric space $Y$
w.r.t. the Lipschitz distance, then $X_{k}\xrightarrow{\operatorname{GH}}Y$.
Does it remain true without the boundedness assumption?

######  Exercise 6.9.

Let the metric space $X_{k}$ be obtained from the standard sphere
$S^{2}\subset\mathbb{R}^{3}$ by removing a ball of radius $1/k$. Prove that
$X_{k}\xrightarrow{\operatorname{GH}}S^{2}$. Prove that if we change $S^{2}$
to the circle $S^{1}$, then the similar statement does not hold. In the both
cases we consider the interior metrics.

##  Chapter 7 Gromov–Hausdorff space.

  * Schedule.

Gromov–Hausdorff space (GH-space), distortions of a correspondence and its
closure, calculating GH-distance in terms of closed correspondences,
compactness of the set of all closed correspondences for compact metric
spaces, continuity of distortion for compact metric spaces, optimal
correspondences, existence of closed optimal correspondences for compact
metric spaces, GH-space is geodesic, cover number and packing number, there
relations, total boundness of families of compact metric spaces in terms of
cover and packing numbers, isometric embedding of all compact metric spaces
from a totally bounded family to the same compact subset of $\ell_{\infty}$,
completeness of GH-space, separability of GH-space,
$\operatorname{mst}$-spectrum in terms of GH-distances to simplexes, Steiner
problem in GH-space.

This section describes some geometrical and topological properties of the
space consisting the isometry classes of compact metric spaces, endowed with
the Gromov–Hausdorff metric.

We denote by $\mathcal{M}$ the set of all compact metric spaces considered up
to isometry (in other words, the set of isometry classes of compact metric
spaces). From Propositions 6.6 and 6.7 it follows that the distance $d_{GH}$
is a metric on $\mathcal{M}$. The metric space $(\mathcal{M},d_{GH})$ is
called _the Gromov–Hausdorff space_. Recall that by $\Delta_{1}$ we denoted a
one-point metric space. Note that $\mathcal{M}$ contains all finite metric
spaces, in particular, $\Delta_{1}\in\mathcal{M}$. The results presented in
Examples 6.28–6.32 lead to the following geometric model of $\mathcal{M}$, see
Figure 7.1.

Figure 7.1: Gromov–Hausdorff space: general properties.

Indeed, according to Example 6.32, the operation of multiplying the metric by
a number $\lambda>0$ is a homothety of the space $\mathcal{M}$, centered in
the one-point metric space $\Delta_{1}$, so $\mathcal{M}$ is a cone with the
vertex $\Delta_{1}$. By Example 6.31, the curves $\gamma(t):=t\,X$,
$X\in\mathcal{M}$, $X\neq\Delta_{1}$, are shortest between any of their
points, so they are the generators of the cone. Figure 7.1 also illustrates
Examples 6.28 and 6.30.

###  7.1 Existence of optimal correspondences between compact metric spaces

Let $X$ and $Y$ be arbitrary metric spaces.

######  Agreement 7.1.

In what follows, when we work with the metric space $X\times Y$, we always
suppose that its distance function is

$\bigl{|}(x,y)(x^{\prime},y^{\prime})\bigr{|}=\max\bigl{\\{}|xx^{\prime}|,\,|yy^{\prime}|\bigr{\\}},$

and just this metric generates the Hausdorff distance on
$\mathcal{P}_{0}(X\times Y)$ and on all its subspaces, e.g., on
$\mathcal{R}(X,Y)$.

######  Problem 7.1.

Prove that the product topology on $X\times Y$ coincides with the one
generated by the metric from Agreement 7.1.

######  Proposition 7.2.

For arbitrary metric spaces $X$ and $Y$, if ${\bar{\sigma}}$ is the closure of
$\sigma\in\mathcal{P}_{0}(X\times Y)$, then
$\operatorname{dis}{\bar{\sigma}}=\operatorname{dis}\sigma$.

###### Proof.

Since $\sigma\subset{\bar{\sigma}}$ then we have
$\operatorname{dis}\sigma\leq\operatorname{dis}{\bar{\sigma}}$, hence in the
case $\operatorname{dis}\sigma=\infty$ the result holds.

Now let $\operatorname{dis}\sigma<\infty$. It remains to prove that
$\operatorname{dis}\sigma\geq\operatorname{dis}{\bar{\sigma}}$.

By definition, for each $\varepsilon>0$ and any
$({\bar{x}},{\bar{y}}),\,({\bar{x}}^{\prime},{\bar{y}}^{\prime})\in{\bar{\sigma}}$
there exist $(x,y),\,(x^{\prime},y^{\prime})\in\sigma$ such that
$\max\bigl{\\{}|{\bar{x}}x|,|{\bar{y}}y|\bigr{\\}}<\varepsilon/6$ and
$\max\bigl{\\{}|{\bar{x}}^{\prime}x^{\prime}|,|{\bar{y}}^{\prime}y^{\prime}|\bigr{\\}}<\varepsilon/6$,
thus
$\bigl{|}|{\bar{x}}{\bar{x}}^{\prime}|-|xx^{\prime}|\bigr{|}<\varepsilon/3$
and
$\bigl{|}|{\bar{y}}{\bar{y}}^{\prime}|-|yy^{\prime}|\bigr{|}<\varepsilon/3$.
Therefore,

$\bigl{|}|{\bar{x}}{\bar{x}}^{\prime}|-|{\bar{y}}{\bar{y}}^{\prime}|\bigr{|}<\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}+2\varepsilon/3\leq\operatorname{dis}\sigma+2\varepsilon/3.$

Passing to the supremum in definition of $\operatorname{dis}{\bar{\sigma}}$,
we conclude that
$\operatorname{dis}{\bar{\sigma}}\leq\operatorname{dis}\sigma+2\varepsilon/3$.
Since $\varepsilon$ is arbitrary, we have
$\operatorname{dis}{\bar{\sigma}}\leq\operatorname{dis}\sigma$. ∎

Denote by $\mathcal{R}_{c}(X,Y)$ the subset of $\mathcal{R}(X,Y)$ consisting
of all closed correspondences $R$. Clearly that for any $R\in\mathcal{R}(X,Y)$
its closure ${\bar{R}}$ is also a correspondence, i.e.,
${\bar{R}}\in\mathcal{R}_{c}(X,Y)$. This fact, together with Proposition 7.2
and Theorem 6.12, immediately implies

######  Corollary 7.3.

For any metric spaces $X$ and $Y$ we have

$d_{GH}(X,Y)=\frac{1}{2}\inf\bigl{\\{}\operatorname{dis}R:R\in\mathcal{R}_{c}(X,Y)\bigr{\\}}.$

Now, let $X$ and $Y$ be compact metric spaces. Then $X\times Y$ is compact as
well, and $\mathcal{R}_{c}(X,Y)\subset\mathcal{H}(X\times Y)$. By Corollary
5.37, $\mathcal{H}(X\times Y)$ is compact.

######  Proposition 7.4.

For $X,\,Y\in\mathcal{M}$ the set $\mathcal{R}_{c}(X,Y)$ is closed in
$\mathcal{H}(X\times Y)$, thus, $\mathcal{R}_{c}(X,Y)$ is compact.

###### Proof.

It suffices to show that for each $\sigma\in\mathcal{H}(X\times
Y)\setminus\mathcal{R}_{c}(X,Y)$ some its neighborhood in $\mathcal{H}(X\times
Y)$ does not intersect $\mathcal{R}_{c}(X,Y)$. Notice that
$\sigma\not\in\mathcal{R}(X,Y)$ because $\mathcal{H}(X\times Y)$ consists of
all closed nonempty subsets of $X\times Y$, and $\mathcal{R}_{c}(X,Y)$ equals
to the set of all closed $R\in\mathcal{R}(X,Y)$. Then either
$\pi_{X}(\sigma)\neq X$, or $\pi_{Y}(\sigma)\neq Y$, where $\pi_{X}$ and
$\pi_{Y}$ are the canonical projections. To be definite, suppose that the
first condition holds, i.e., there exists $x\in X\setminus\pi_{X}(\sigma)$.
Since $\sigma$ is a closed subset of the compact $X\times Y$, then it is
compact itself, and therefore $\pi_{X}(\sigma)$ is compact in $X$, thus,
$\pi_{X}(\sigma)$ is closed. The latter implies that there exists an open ball
$U_{\varepsilon}(x)$ such that
$U_{\varepsilon}(x)\cap\pi_{X}(\sigma)=\emptyset$. Let
$U=U_{\varepsilon/2}^{\mathcal{H}(X\times Y)}(\sigma)$, then for each
$\sigma^{\prime}\in U$ we have $d_{H}(\sigma,\sigma^{\prime})<\varepsilon/2$,
thus for any $(a^{\prime},b^{\prime})\in\sigma^{\prime}$ there exists
$(a,b)\in\sigma$ such that
$\bigl{|}(a,b),(a^{\prime},b^{\prime})\bigr{|}<\varepsilon/2$. Since
$a\in\pi_{X}(\sigma)$ then $|xa|\geq\varepsilon$. On the other hand,
$|aa^{\prime}|\leq\bigl{|}(a,b),(a^{\prime},b^{\prime})\bigr{|}<\varepsilon/2$,
therefore, $|xa^{\prime}|>\varepsilon/2$, i.e., $a^{\prime}\not\in
U_{\varepsilon/2}(x)$ and hence $\pi_{X}(\sigma^{\prime})\cap
U_{\varepsilon/2}(x)=\emptyset$. This implies that $\sigma^{\prime}$ is not a
correspondence, thus $\sigma^{\prime}\not\in\mathcal{R}_{c}(X,Y)$ and
$U\cap\mathcal{R}_{c}(X,Y)=\emptyset$. ∎

Define a function $f\colon(X\times Y)\times(X\times Y)\to\mathbb{R}$ as
$f(x,y,x^{\prime},y^{\prime})=\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}$.
Clearly that $f$ is continuous. Notice that for each
$\sigma\in\mathcal{P}_{0}(X\times Y)$ we have

$\operatorname{dis}\sigma=\sup\bigl{\\{}f(x,y,x^{\prime},y^{\prime}):(x,y),\,(x^{\prime},y^{\prime})\in\sigma\bigr{\\}}=\sup
f|_{\sigma\times\sigma}.$

######  Proposition 7.5.

If $X,\,Y\in\mathcal{M}$, then the function
$\operatorname{dis}\colon\mathcal{H}(X\times Y)\to\mathbb{R}$ is continuous.

###### Proof.

Since $(X\times Y)\times(X\times Y)$ is compact, then the function $f$ is
uniformly continuous, i.e., for any $\varepsilon>0$ there exists $\delta>0$
such that for every $(x_{1},y_{1},x^{\prime}_{1},y^{\prime}_{1})$ and
$(x_{2},y_{2},x^{\prime}_{2},y^{\prime}_{2})$ with
$\max\bigl{\\{}|x_{1}x_{2}|,|y_{1},y_{2}|,|x^{\prime}_{1}x^{\prime}_{2}|,|y^{\prime}_{1}y^{\prime}_{2}|\bigr{\\}}<\delta$
it holds

$\bigl{|}f(x_{1},y_{1},x^{\prime}_{1},y^{\prime}_{1})-f(x_{2},y_{2},x^{\prime}_{2},y^{\prime}_{2})\bigr{|}<\varepsilon.$

Thus, for any $\sigma\in\mathcal{H}(X\times Y)$ and any $\varepsilon>0$ there
exists $\delta>0$ such that for the open $\delta$-neighborhood
$U=U_{\delta}^{X\times Y}(\sigma)\subset X\times Y$ of $\sigma$ it holds

$\sup f|_{U\times U}\leq\sup f|_{\sigma\times\sigma}+\varepsilon.$

By $V$ we denote the open ball $U_{\delta}^{\mathcal{H}(X\times
Y)}(\sigma)\subset\mathcal{H}(X\times Y)$ of radius $\delta$ centered at
$\sigma$. Since for any $\sigma^{\prime}\in V$ we have $\sigma^{\prime}\subset
U$, then it follows that

$\operatorname{dis}\sigma^{\prime}=\sup
f|_{\sigma^{\prime}\times\sigma^{\prime}}\leq\sup f|_{U\times U}\leq\sup
f|_{\sigma\times\sigma}+\varepsilon=\operatorname{dis}\sigma+\varepsilon.$

Swapping $\sigma$ and $\sigma^{\prime}$, we get
$|\operatorname{dis}\sigma-\operatorname{dis}\sigma^{\prime}|\leq\varepsilon$,
and hence, the function $\operatorname{dis}$ is continuous. ∎

######  Definition 7.6.

A correspondence $R\in\mathcal{R}(X,Y)$ is called _optimal_ if
$d_{GH}(X,Y)=\frac{1}{2}\operatorname{dis}R$. By
$\mathcal{R}_{\operatorname{opt}}(X,Y)$ we denote the set of all optimal
correspondences between $X$ and $Y$.

######  Theorem 7.7.

For any $X,\,Y\in\mathcal{M}$ we have
$\mathcal{R}_{\operatorname{opt}}(X,Y)\cap\mathcal{R}_{c}(X,Y)\neq\emptyset$.

###### Proof.

By Proposition 7.5, the function
$\operatorname{dis}\colon\mathcal{R}_{c}(X,Y)\to\mathbb{R}$ is continuous, and
by Proposition 7.4 the space $\mathcal{R}_{c}(X,Y)$ is compact, thus the
function $\operatorname{dis}$ attains its least value. The half of this value
equals $d_{GH}(X,Y)$, and each correspondence $R$ which this least value is
attained at is optimal. ∎

From Theorem 7.7 and Propositions 6.11 and 6.11, we immediately get

######  Corollary 7.8.

For each nonisometric $X,\,Y\in\mathcal{M}$ there exist

  1. (1)

a correspondence $R\in\mathcal{R}_{c}(X,Y)$ such that
$d_{GH}(X,Y)=\frac{1}{2}\operatorname{dis}R$_;_

  2. (2)

an admissible metric $\rho\in\mathcal{D}(X,Y)$ such that
$d_{GH}(X,Y)=\rho_{H}(X,Y)$_;_

  3. (3)

a metric space $Z$ and isometric embeddings of $X$ and $Y$ into $Z$ such that
the Hausdorff distance between their images equals $d_{GH}(X,Y)$.

###  7.2 The Gromov–Hausdorff space is geodesic

Let $X$ and $Y$ be arbitrary metric spaces. We assume that the space $X\times
Y$ is by default endowed with the metric

$\bigl{|}(x,y)(x^{\prime},y^{\prime})\bigr{|}=\max\bigl{\\{}|xx^{\prime}|,|yy^{\prime}|\bigr{\\}}.$

Also, we introduce on $X\times Y$ the following $1$-parametric family of
metrics $d_{t}$, $t\in(0,1)$:

$d_{t}\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}=(1-t)|xx^{\prime}|+t|yy^{\prime}|.$

######  Problem 7.2.

Prove that the topologies generated by all $d_{t}$, and by $|\cdot|$ as well,
coincide with the product topology of $X\times Y$.

Now we suppose that $d_{GH}(X,Y)<\infty$, and $R\in\mathcal{R}(X,Y)$ is any
correspondence with $\operatorname{dis}R<\infty$. By $R_{t}$, $t\in[0,1]$, we
denote the metric space $(R,d_{t})$ if $t\in(0,1)$, and we put $R_{0}=X$,
$R_{1}=Y$.

######  Proposition 7.9.

The mapping $t\mapsto R_{t}$ is Lipschitzian with the Lipschitz constant
$\frac{1}{2}\operatorname{dis}R$ _(_ w.r.t. the Gromov–Hausdorff distance _)_.

###### Proof.

We have to show that $2d_{GH}(R_{s},R_{t})\leq|s-t|\operatorname{dis}R$ for
arbitrary $s,t\in[0,1]$. Let us start with the case $0<s,t<1$. As always, we
denote by $\operatorname{id}$ the identical mapping. Then

$2d_{GH}(R_{s},R_{t})\leq\operatorname{dis}\operatorname{id}=\sup\biggl{\\{}\Bigl{|}d_{s}\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}-d_{t}\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}\Bigr{|}:(x,y),(x^{\prime},y^{\prime})\in
R\biggr{\\}}=\\\
=|s-t|\sup\Bigl{\\{}\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}:(x,y),(x^{\prime},y^{\prime})\in
R\Bigr{\\}}=|s-t|\operatorname{dis}R.$

Now we consider the case $s=0$, $0<t<1$. As a correspondence we take
$S_{t}\in\mathcal{R}(R_{0},R_{t})$ of the form

$S_{t}=\bigcup_{(x,y)\in R}\Bigl{\\{}\bigl{(}x,(x,y)\bigr{)}\Bigr{\\}}.$

Notice that such $S_{t}$ does not depend on $t$ as a set. We have

$2d_{GH}(R_{0},R_{t})\leq\operatorname{dis}S_{t}=\sup\biggl{\\{}\Bigl{|}|xx^{\prime}|-d_{t}\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}\Bigr{|}:\bigl{(}x,(x,y)\bigr{)},\bigl{(}x^{\prime},(x^{\prime},y^{\prime})\bigr{)}\in
S_{t}\biggr{\\}}=\\\
=t\sup\Bigl{\\{}\bigl{|}|xx^{\prime}|-|yy^{\prime}|\bigr{|}:\bigl{(}x,(x,y)\bigr{)},\bigl{(}x^{\prime},(x^{\prime},y^{\prime})\bigr{)}\in
S_{t}\Bigr{\\}}=t\operatorname{dis}R=|s-t|\operatorname{dis}R.$

All remaining cases can be proved similarly. ∎

Now, let $X$ and $Y$ be compact metric spaces, and $R\in\mathcal{R}_{c}(X,Y)$.
Then $R$ is compact as well, and by Problem 7.2, all metric spaces $R_{t}$ are
compact too. Thus, by Proposition 7.9, the mapping $t\mapsto R_{t}$ is a
Lipschitz curve in $\mathcal{M}$, and it joins $X$ and $Y$.

######  Theorem 7.10.

Given $X,Y\in\mathcal{M}$ and
$R\in\mathcal{R}_{\operatorname{opt}}(X,Y)\cap\mathcal{R}_{c}(X,Y)$, the curve
$\gamma\colon[0,1]\to\mathcal{M}$, $\gamma\colon t\mapsto R_{t}$, is a
shortest geodesic with the speed $d_{GH}(X,Y)$. In particular, the length of
$\gamma$ equals to $d_{GH}(X,Y)$, thus, the space $\mathcal{M}$ is geodesic.

###### Proof.

Choose arbitrary $0\leq s\leq t\leq 1$, then, by Proposition 7.9, we have

(7.1)
$d_{GH}(R_{s},R_{t})\leq\frac{t-s}{2}\operatorname{dis}R=(t-s)\,d_{GH}(X,Y),$

thus, taking into account the triangle inequality, we get

$d_{GH}(X,Y)\leq d_{GH}(X,R_{s})+d_{GH}(R_{s},R_{t})+d_{GH}(R_{t},Y)\leq
d_{GH}(X,Y),$

therefore, $d_{GH}(X,R_{s})+d_{GH}(R_{s},R_{t})+d_{GH}(R_{t},Y)=d_{GH}(X,Y)$.
If for some $s$ and $t$ the inequality in Formula (7.1) is strict, then the
previous equality is not satisfied, thus
$d_{GH}(R_{s},R_{t})=(t-s)\,d_{GH}(X,Y)$. It remains to note that

$|\gamma|=\sup_{0=t_{0}<\cdots<t_{n}=1}\sum_{i=1}^{n}d_{GH}(R_{t_{i-1}},R_{t_{i}})=d_{GH}(X,Y),$

hence $\gamma$ is shortest. ∎

###  7.3 Cover number and packing number

Let $X$ be an arbitrary metric space and $\varepsilon>0$. The numerical
characteristics of the pair $(X,\varepsilon)$ defined below will be used by us
in the study of totally bounded families of compact metric spaces, in
particular, in terms of these numbers, the Gromov criterion for the
precompactness of a family of compact metric spaces will be formulated.

######  Definition 7.11.

_The cover number_

$\operatorname{cov}(X,\varepsilon)=\inf\Bigl{\\{}n\in{\mathbb{N}}:\exists\,x_{1},\ldots,x_{n}\in
X,\ \ X=\bigcup_{i=1}^{n}U_{\varepsilon}(x_{i})\Bigr{\\}}$

(as usually, we put $\inf\emptyset=\infty$). In other words, the cover number
is the minimum number of open balls of radius $\varepsilon$ that cover the
space $X$.

_The packing number_

$\operatorname{pack}(X,\varepsilon)=\sup\bigl{\\{}n\in{\mathbb{N}}:\exists\,x_{1},\ldots,x_{n}\in
X\,\forall\,i\neq j\ \ U_{\varepsilon/2}(x_{i})\cap
U_{\varepsilon/2}(x_{j})=\emptyset\bigr{\\}}.$

In other words, the packing number is the maximum number of open pairwise
disjoint balls of radius $\varepsilon/2$ in the space $X$.

######  Problem 7.3.

Prove that

  1. (1)

a metric space $X$ is bounded if only for some $\varepsilon>0$ it holds
$\operatorname{cov}(X,\varepsilon)<\infty$ (similarly,
$\operatorname{pack}(X,\varepsilon)<\infty$);

  2. (2)

a metric space $X$ is finite if and only if there exists $n$ such that
$\operatorname{cov}(X,\varepsilon)\leq n$ for all $\varepsilon>0$ (similarly,
for $\operatorname{pack}(X,\varepsilon)$);

  3. (3)

the functions $f(\varepsilon)=\operatorname{cov}(X,\varepsilon)$ and
$g(\varepsilon)=\operatorname{pack}(X,\varepsilon)$ are monotonically
decreasing.

######  Proposition 7.12.

For any metric space $X$ and any number $\varepsilon>0$ we have

$\operatorname{cov}(X,\varepsilon)\leq\operatorname{pack}(X,\varepsilon)\leq\operatorname{cov}(X,\varepsilon/4).$

###### Proof.

First we prove the first inequality. If
$\operatorname{pack}(X,\varepsilon)=\infty$, then the inequality is
automatically satisfied. Now let $\operatorname{pack}(X,\varepsilon)<\infty$
and $x_{1},\ldots,x_{n}$, $n=\operatorname{pack}(X,\varepsilon)$, be a largest
set of points in $X$ for which the balls $U_{\varepsilon/2}(x_{i})$ are
disjoint. Since this family is maximal, for any $x\in X$ there exists $x_{k}$
such that $U_{\varepsilon/2}(x)\cap U_{\varepsilon/2}(x_{k})\neq\emptyset$,
i.e., $|xx_{k}|<\varepsilon$. Then the family
$\\{U_{\varepsilon}(x_{i})\\}_{i=1}^{n}$ covers $X$, so
$\operatorname{cov}(X,\varepsilon)\leq n=\operatorname{pack}(X,\varepsilon)$.

Let us prove the second inequality. Again, if
$\operatorname{cov}(X,\varepsilon/4)=\infty$, then the inequality holds. Now
let $\operatorname{cov}(X,\varepsilon/4)<\infty$ and $x_{1},\ldots,x_{m}$,
$m=\operatorname{cov}(X,\varepsilon/4)$, be the smallest set of points in $X$
for which the balls $U_{\varepsilon/4}(x_{i})$ cover $X$. Suppose that
$\operatorname{pack}(X,\varepsilon)>\operatorname{cov}(X,\varepsilon/4)$, then
there exist $x^{\prime}_{1},\ldots,x^{\prime}_{n}$,
$n>\operatorname{cov}(X,\varepsilon/4)$, such that the balls
$U_{\varepsilon/2}(x^{\prime}_{i})$ are pairwise disjoint. On the other hand,
for some $i\neq j$ there exists $k$ such that
$x^{\prime}_{i},x^{\prime}_{j}\in U_{\varepsilon/4}(x_{k})$, therefore,
$x_{k}\in U_{\varepsilon/2}(x^{\prime}_{i})\cap
U_{\varepsilon/2}(x^{\prime}_{j})$, so this intersection is not empty, a
contradiction. ∎

######  Corollary 7.13.

Let $X$ be an arbitrary metric space, then

  1. (1)

if $\operatorname{pack}(X,\varepsilon)<\infty$, then
$\operatorname{cov}(X,\varepsilon)<\infty$_;_

  2. (2)

if $\operatorname{cov}(X,\varepsilon)<\infty$, then
$\operatorname{pack}(X,4\varepsilon)<\infty$.

Thus, $\operatorname{cov}(X,\varepsilon)<\infty$ for all $\varepsilon>0$, if
and only if $\operatorname{pack}(X,\varepsilon)<\infty$ for all
$\varepsilon>0$.

######  Proposition 7.14.

Let $X$ be an arbitrary metric space. Then the following statements are
equivalent _:_

  1. (1)

$\operatorname{cov}(X,\varepsilon)<\infty$ for any $\varepsilon>0$_;_

  2. (2)

$\operatorname{pack}(X,\varepsilon)<\infty$ for any $\varepsilon>0$_;_

  3. (3)

the space $X$ is totally bounded.

###### Proof.

$(\ref{prop:CovParkTotalBound:1})\Leftrightarrow(\ref{prop:CovParkTotalBound:2})$
This follows from Corollary 7.13.

$(\ref{prop:CovParkTotalBound:1})\Leftrightarrow(\ref{prop:CovParkTotalBound:3})$
The condition $\operatorname{cov}(X,\varepsilon)<\infty$ is equivalent to the
existence of a finite cover $\\{U_{\varepsilon}(x_{i})\\}_{i=1}^{n}$, which is
equivalent to the existence of a finite $\varepsilon$-net
$\\{x_{i}\\}_{i=1}^{n}$. Thus, the condition of Item (1) is equivalent to the
total boundedness of the space $X$. ∎

######  Proposition 7.15.

Let $X$, $Y$ be metric spaces, $\delta>0$, and $d_{GH}(X,Y)<\delta$, then

  1. (1)

$\operatorname{cov}(X,\varepsilon)\geq\operatorname{cov}(Y,\varepsilon+2\delta)$,

  2. (2)

$\operatorname{pack}(X,\varepsilon)\geq\operatorname{pack}(Y,2\varepsilon+4\delta)$.

###### Proof.

(1) The case $\operatorname{cov}(X,\varepsilon)=\infty$ is obvious. Now let
$m:=\operatorname{cov}(X,\varepsilon)<\infty$ and
$\bigl{\\{}U_{\varepsilon}(x_{i})\bigr{\\}}_{i=1}^{m}$ be a cover of $X$. By
Theorem 6.12, there exists $R\in\mathcal{R}(X,Y)$ such that
$\operatorname{dis}R<2\delta$. For each $i$, we choose an arbitrary $y_{i}\in
R(x_{i})$ and show that the set $\\{y_{i}\\}_{i=1}^{m}$ is an
$(\varepsilon+2\delta)$-net, thus
$\operatorname{cov}(Y,\varepsilon+2\delta)\leq
m=\operatorname{cov}(X,\varepsilon)$. So, we take arbitrary $y\in Y$ and
choose any $x\in R^{-1}(y)$. Then for some $j$ we have $|xx_{j}|<\varepsilon$.
Since $\operatorname{dis}R<2\delta$, then $|yy_{j}|<\varepsilon+2\delta$, as
required.

(2) Since the case $\operatorname{pack}(Y,2\varepsilon+4\delta)=\infty$ is
trivial, we assume that
$n:=\operatorname{pack}(Y,2\varepsilon+4\delta)<\infty$ and let
$\bigl{\\{}U_{\varepsilon+2\delta}(y_{i})\bigr{\\}}_{i=1}^{n}$ be a disjoint
family of open balls in $Y$. Then for any $i\neq j$ we have
$|y_{i}y_{j}|\geq\varepsilon+2\delta$. For each $i$, we choose an arbitrary
$x_{i}\in R^{-1}(y_{i})$. Since $\operatorname{dis}R<2\delta$, we have
$|x_{i}x_{j}|>\varepsilon$, therefore the family
$\bigl{\\{}U_{\varepsilon/2}(x_{i})\bigr{\\}}_{i=1}^{n}$ is disjoint and,
thus, $\operatorname{pack}(X,\varepsilon)\geq
n=\operatorname{pack}(Y,2\varepsilon+4\delta)$. ∎

###  7.4 Totally bounded families of compact metric spaces

We will be interested in when a particular family of compact metric spaces is
totally bounded. We begin with the following auxiliary statement, which will
be needed below. For $n\in{\mathbb{N}}$ we denote by
$\mathcal{M}_{n}\subset\mathcal{M}$ ($\mathcal{M}_{[n]}\subset\mathcal{M}$)
the set of all metric spaces with at most (respectively, exact) $n$ points.
For $D\geq 0$, by $\mathcal{M}(D)\subset\mathcal{M}$ we denote the set of all
compact metric spaces whose diameters do not exceed $D$. We also put
$\mathcal{M}_{n}(D)=\mathcal{M}_{n}\cap\mathcal{M}(D)$ and
$\mathcal{M}_{[n]}(D)=\mathcal{M}_{[n]}\cap\mathcal{M}(D)$. It is clear that
$\mathcal{M}_{n}=\cup_{k\leq n}\mathcal{M}_{[k]}$ and
$\mathcal{M}_{n}(D)=\cup_{k\leq n}\mathcal{M}_{[k]}(D)$.

######  Proposition 7.16.

The space $\mathcal{M}_{[n]}(D)\subset\mathcal{M}$ is totally bounded.

###### Proof.

Given $X\in\mathcal{M}_{[n]}(D)$, we consider all possible bijections
$\nu\colon X\to\\{1,\ldots,n\\}$, and for every such $\nu$ we construct the
distance matrix $f(X,\nu)=\rho=(\rho_{ij})$, where
$\rho_{ij}=\bigl{|}\nu^{-1}(i)\nu^{-1}(j)\bigr{|}$. Let $T$ be the set of all
such matrices. It is clear that the mapping $g\colon T\to\mathcal{M}_{[n]}(D)$
such that $g\colon f(X,\nu)\mapsto X$ is surjective.

We define on $T$ the distance function generated by the $\ell_{\infty}$-norm,
so $T$ will be considered as a subset of $\mathbb{R}^{n^{2}}_{\infty}$. Since
for every $i,j$ we have $|\rho_{ij}|\leq D$, the set $T$ is bounded and,
therefore, totally bounded as a subset of $\mathbb{R}^{n^{2}}_{\infty}$.

If $X,X^{\prime}\in\mathcal{M}_{[n]}(D)$, $\rho=f(X,\nu)$ and
$\rho^{\prime}=f(X^{\prime},\nu^{\prime})$, then
$R=(\nu^{\prime})^{-1}\circ\nu$ is a bijective correspondence between $X$ and
$X^{\prime}$, and $|\rho\rho^{\prime}|_{\infty}=\operatorname{dis}R\geq
2d_{GH}(X,X^{\prime})$. Thus, the surjection $g$ is Lipschitzian, therefore,
$\mathcal{M}_{[n]}(D)=g(T)$ is also totally bounded. ∎

######  Corollary 7.17.

The space $\mathcal{M}_{n}(D)\subset\mathcal{M}$ is totally bounded.

######  Problem 7.4.

Prove that the set $\mathcal{M}_{n}(D)$ is compact, while
$\mathcal{M}_{[n]}(D)$ for $n>1$ is not.

######  Theorem 7.18.

Let $\mathcal{C}$ be a nonempty subset of $\mathcal{M}$. Then the following
statements are equivalent.

  1. (1)

There is a number $D\geq 0$ and a function $N\colon(0,\infty)\to{\mathbb{N}}$
such that for all $X\in\mathcal{C}$ we have $\operatorname{diam}X\leq D$ and
$\operatorname{pack}(X,\varepsilon)\leq N(\varepsilon)$.

  2. (2)

There is a number $D\geq 0$ and a function $N\colon(0,\infty)\to{\mathbb{N}}$
such that for all $X\in\mathcal{C}$ we have $\operatorname{diam}X\leq D$ and
$\operatorname{cov}(X,\varepsilon)\leq N(\varepsilon)$.

  3. (3)

The space $\mathcal{C}$ with the metric $d_{GH}$ is totally bounded.

###### Proof.

$(\ref{thm:GromovPrecomp:3})\Rightarrow(\ref{thm:GromovPrecomp:1})$. Fix an
arbitrary $\varepsilon>0$. We have to find the corresponding $D$ and
$N(\varepsilon)$. Since $\mathcal{C}$ is totally bounded, for any $\delta>0$
there exists a finite $\delta$-net $\mathcal{C}^{\prime}\subset\mathcal{C}$.
Choose $\delta$ such that $4\delta<\varepsilon$. Since all the spaces lying in
$\mathcal{C}^{\prime}$ are totally bounded, by Proposition 7.14, their packing
numbers are finite. In addition, their diameters are finite. Put
$D^{\prime}=\max_{X^{\prime}\in\mathcal{C}^{\prime}}\operatorname{diam}X^{\prime}$
and
$N^{\prime}(\varepsilon)=\max_{X^{\prime}\in\mathcal{C}^{\prime}}\operatorname{pack}(X^{\prime},\varepsilon)$.
For an arbitrary $X\in\mathcal{C}$ there exists
$X^{\prime}\in\mathcal{C}^{\prime}$ such that $d_{GH}(X,X^{\prime})<\delta$.
It is easy to see that
$\operatorname{diam}X\leq\operatorname{diam}X^{\prime}+2\delta\leq
D^{\prime}+2\delta$, so that we can put $D=D^{\prime}+2\delta$. In addition,
by Proposition 7.15, it holds
$\operatorname{pack}(X,\varepsilon)\leq\operatorname{pack}(X^{\prime},\varepsilon/2-2\delta)\leq
N^{\prime}(\varepsilon/2-2\delta)$, so we can put
$N(\varepsilon)=N^{\prime}(\varepsilon/2-2\delta)$.

$(\ref{thm:GromovPrecomp:1})\Leftrightarrow(\ref{thm:GromovPrecomp:2})$. This
immediately follows from Proposition 7.12.

$(\ref{thm:GromovPrecomp:2})\Rightarrow(\ref{thm:GromovPrecomp:3})$. Fix some
$\varepsilon>0$, and for each $X\in\mathcal{C}$ consider a finite cover of the
space $X$ by at most $n=N(\varepsilon)$ open balls of radius $\varepsilon$. By
$F_{X}^{\varepsilon}$ we denote the set of centers of these balls, then
$d_{GH}(X,F_{X}^{\varepsilon})\leq\varepsilon$. In addition,
$F_{X}^{\varepsilon}\in\mathcal{M}_{n}(D)$, therefore, by Corollary 7.17, the
family
$\mathcal{F}^{\varepsilon}=\\{F_{X}^{\varepsilon}\\}_{X\in\mathcal{C}}\subset\mathcal{M}_{n}(D)$
is totally bounded. Since for any $X\in\mathcal{C}$ and any
$\varepsilon^{\prime}>\varepsilon$ we have $X\in
U^{\mathcal{M}}_{\varepsilon^{\prime}}(F^{\varepsilon}_{X})$, then
$\mathcal{C}\subset
U^{\mathcal{M}}_{\varepsilon^{\prime}}(\mathcal{F}^{\varepsilon})$. Since
$\varepsilon$ and $\varepsilon^{\prime}$ are arbitrary, we conclude that
$\mathcal{C}$ is also totally bounded (verify that). ∎

The following theorem allows us to realize all metric spaces from a totally
bounded subset of $\mathcal{M}$ as subsets of some compact subset of
$\ell_{\infty}$.

######  Theorem 7.19 (Gromov).

For each totally bounded family $\mathcal{C}\subset\mathcal{M}$ there exists a
compact $K\subset\ell_{\infty}$ such that every $X\in\mathcal{C}$ is
isometrically embedded into $K$.

###### Proof.

The compact $K$ is constructed as follows. By Theorem 7.18, there exist $D\geq
0$ and $N\colon(0,\infty)\to{\mathbb{N}}$ such that for all $X\in\mathcal{C}$
we have $\operatorname{diam}X\leq D$ and
$\operatorname{cov}(X,\varepsilon)\leq N(\varepsilon)$. Choose an arbitrary
decreasing sequence of positive numbers
$E=\\{\varepsilon_{1},\varepsilon_{2},\ldots\\}$ such that
$\sum_{i=1}^{\infty}\varepsilon_{i}<\infty$. This sequence and the function
$N(\varepsilon)$ generate a sequence of natural numbers
$N_{i}=N(\varepsilon_{i})$. These two sequences, together with the number $D$,
define the set $F_{D,E}\subset\ell_{\infty}$ as follows.

######  Construction 7.1.

Put
$A=\cup_{j=1}^{\infty}\bigl{(}\\{1,\ldots,N_{1}\\}\times\cdots\times\\{1,\ldots,N_{j}\\}\bigr{)}$.
It is clear that $A$ is a countable set. Let $\ell_{\infty}(A)=\\{f\colon
A\to\mathbb{R}:\sup|f|<\infty\\}$, then $\ell_{\infty}(A)$ is isometric to
$\ell_{\infty}$. For brevity, instead of
$f\bigl{(}(n_{1},\ldots,n_{j})\bigr{)}$ we will write $f(n_{1},\ldots,n_{j})$.

We now define the set $F_{D,E}$, composing it from all $f\colon
A\to\mathbb{R}$ that satisfy the following conditions:

  1. (1)

$0\leq f(n_{1})\leq D$ for all $1\leq n_{1}\leq N_{1}$;

  2. (2)

$\bigl{|}f(n_{1},\ldots,n_{j},n_{j+1})-f(n_{1},\ldots,n_{j})\bigr{|}\leq\varepsilon_{j}$
for all elements $(n_{1},\ldots,n_{j},n_{j+1})\in A$.

######  Lemma 7.20.

The set $F_{D,E}$ defined above is a compact subset of $\ell_{\infty}(A)$.

###### Proof.

First, note that for each function $f\in F_{D,E}$ it holds $\sup_{a\in
A}\bigl{|}f(a)\bigr{|}\leq D+\sum_{i=1}^{\infty}\varepsilon_{i}<\infty$, so
$f\in\ell_{\infty}(A)$. Further, since all the inequalities defining $F_{D,E}$
are non-strict, the set $F_{D,E}$ is closed in $\ell_{\infty}(A)$. Since
$\ell_{\infty}(A)$ is complete, $F_{D,E}$ is also complete. In addition, the
diameter of $F_{D,E}$ is finite (it bounded by the number
$D+2\sum_{i=1}^{\infty}\varepsilon_{i}$).

Put $A_{[k]}=\bigl{\\{}(n_{1},\ldots,n_{k})\in A\bigr{\\}}$ and
$A_{k}=\cup_{j=1}^{k}A_{j}$. We denote by
$\pi_{k}\colon\ell_{\infty}(A)\to\ell_{\infty}(A_{k})$ the canonical
projection that maps each function $f\colon A\to\mathbb{R}$ to its restriction
on $A_{k}\subset A$, and let $F_{k}=\pi_{k}(F_{D,E})$. Note that $F_{k}$ is a
closed and bounded subset of the finite-dimensional vector space
$\ell_{\infty}(A_{k})$, therefore $F_{k}$ is compact.

Define the mapping $\nu\colon F_{k}\to\ell_{\infty}(A)$ by extending each
function $f_{k}\in F_{k}$ to the entire set $A$ as follows:

$f_{k}(n_{1},\ldots,n_{k},n_{k+1},\ldots)=f_{k}(n_{1},\ldots,n_{k}).$

It is clear that $\nu$ is isometric, therefore $F^{\prime}_{k}=\nu(F_{k})$ is
also a compact set.

Put $e_{k}=\varepsilon_{k}+\varepsilon_{k+1}+\ldots$, then $e_{k}\to\emptyset$
as $k\to\infty$. By Condition (2), we have $F_{D,E}\subset
U^{\ell_{\infty}(A)}_{e_{k}}(F^{\prime}_{k})$ for all $k\geq 2$, which implies
the total boundedness of $F_{D,E}$ (verify that). ∎

We now take the set $F_{D,2E}$ as $K$ and show that each space
$X\in\mathcal{C}$ can be isometrically embedded into this $K$. We consider
points of the form $x_{a}$, $a\in A$, and again, for brevity, instead of
$x_{(n_{1},\ldots,n_{j})}$ we write $x_{n_{1}\cdots n_{j}}$.

Take an arbitrary $X\in\mathcal{C}$. Since
$\operatorname{cov}(X,\varepsilon_{1})\leq N(\varepsilon_{1})=N_{1}$, then $X$
contains an $\varepsilon_{1}$-net
$\cup_{n_{1}=1}^{N_{1}}\bigl{\\{}x_{n_{1}}\bigr{\\}}$, i.e., the family
$\bigl{\\{}U_{\varepsilon_{1}}(x_{n_{1}})\bigr{\\}}_{n_{1}=1}^{N_{1}}$ forms a
cover of $X$. Note that some points $x_{n_{1}}$ may coincide.

Further, since $\operatorname{cov}(X,\varepsilon_{2})\leq
N(\varepsilon_{2})=N_{2}$, then $X$ contains an $\varepsilon_{2}$-net
$\cup_{n_{2}=1}^{N_{2}}\bigl{\\{}x^{\prime}_{n_{2}}\bigr{\\}}$, i.e., the
family
$\bigl{\\{}U_{\varepsilon_{2}}(x^{\prime}_{n_{2}})\bigr{\\}}_{n_{2}=1}^{N_{2}}$
forms a cover of $X$. Fix $n_{1}$ and choose only those balls
$U_{\varepsilon_{2}}(x^{\prime}_{n_{2}})$ that satisfy
$|x_{n_{1}}x^{\prime}_{n_{2}}|<\varepsilon_{1}+\varepsilon_{2}$. In this way
we have got at most $N_{2}$ balls. Enumerate them and add some copies of them
to obtain exactly $N_{2}$ balls which we denote by
$U_{\varepsilon_{2}}(x_{n_{1}n_{2}})$, $n_{2}=1,\ldots,N_{2}$. So, we have got
a cover
$\bigl{\\{}U_{\varepsilon_{2}}(x_{n_{1}n_{2}})\bigr{\\}}_{n_{2}=1}^{N_{2}}$ of
the ball $U_{\varepsilon_{1}}(x_{n_{1}})$. By construction, it holds
$|x_{n_{1}}x_{n_{1}n_{2}}|<\varepsilon_{1}+\varepsilon_{2}<2\varepsilon_{1}$.

Continuing this process, at the $j$-th step we get the family of balls
$\bigl{\\{}U_{\varepsilon_{j}}(x_{a})\bigr{\\}}_{a\in A_{[j]}}$ with
$|x_{n_{1}\cdots n_{j}}x_{n_{1}\cdots n_{j}n_{j+1}}|<2\varepsilon_{j}$.

It is easy to see that the set $\\{x_{a}\\}_{a\in A}$ of centers of these
balls is a countable everywhere dense subset of $X$ (some $x_{a}$ may coincide
with each other). By Theorem 2.26, the space $X$ can be isometrically embedded
into $\ell_{\infty}(A)$ by associating with each point $x$ the function
$f_{x}\colon A\to\mathbb{R}$ defined as follows: $f_{x}(a)=|xx_{a}|$.

######  Lemma 7.21.

For every $x\in X$ we have $f_{x}\in F_{D,2E}$.

###### Proof.

It is clear that $0\leq f_{x}\leq D$, so that Item (1) from the definition of
the set $F_{D,2E}$ is satisfied. Further, for each
$(n_{1},\ldots,n_{j},n_{j+1})$, the point $x_{n_{1}\cdots n_{j}n_{j+1}}$ lies
in $U_{2\varepsilon_{j}}(x_{n_{1}\cdots n_{j}})$, so for every $x\in X$ we
have

$\bigl{|}f_{x}(n_{1},\ldots,n_{j},n_{j+1})-f_{x}(n_{1},\ldots,n_{j})\bigr{|}=\bigl{|}|x_{n_{1}\cdots
n_{j}n_{j+1}}x|-|x_{n_{1}\cdots n_{j}}x|\bigr{|}\leq|x_{n_{1}\cdots
n_{j}n_{j+1}}x_{n_{1}\cdots n_{j}}|<2\varepsilon_{j},$

therefore, Item (2) from the definition of the set $F_{D,2E}$ is also
fulfilled. ∎

Thus, the mapping $x\mapsto f_{x}$ isometrically embeds $X$ into $K$. ∎

###  7.5 Some other properties of Gromov–Hausdorff space

In this section we apply the previous results to prove a few more properties
of the Gromov–Hausdorff space $\mathcal{M}$.

####  7.5.1 Completeness of Gromov–Hausdorff space

Theorem 7.19 implies the following result.

######  Theorem 7.22.

The space $\mathcal{M}$ is complete.

###### Proof.

Consider an arbitrary fundamental sequence
$\\{X_{i}\\}_{i=1}^{\infty}\subset\mathcal{M}$. Then
$\\{X_{i}\\}_{i=1}^{\infty}$ is a totally bounded subset of $\mathcal{M}$. By
Theorem 7.19, there exists a compact set $K\subset\ell_{\infty}$ into which
all $X_{i}$ can be isometrically embedded. Denote by $Y_{i}$ the image of
$X_{i}$. By Theorem 5.38, the space $\mathcal{H}(K)$ of all closed bounded
subsets of $K$ is also compact, therefore the sequence
$Y_{i}\in\mathcal{H}(K)$ contains a convergent subsequence $Y_{n_{i}}$. Let
$Y$ be the limit of this subsequence. Then $Y$ is a nonempty compact metric
space and

$d_{GH}(X_{n_{i}},Y)=d_{GH}(Y_{n_{i}},Y)\leq d_{H}(Y_{n_{i}},Y)\to 0\ \
\text{as $i\to\infty$},$

therefore, $X_{n_{i}}\xrightarrow{\operatorname{GH}}Y$ and, since the sequence
$X_{i}$ is fundamental, we have $X_{i}\xrightarrow{\operatorname{GH}}Y$. ∎

####  7.5.2 Separability of Gromov–Hausdorff space

######  Theorem 7.23.

The space $\mathcal{M}$ is separable.

###### Proof.

By Corollary 7.17, each space $\mathcal{M}_{n}(D)$ is totally bounded and,
therefore, separable. Since
$\mathcal{M}_{n}=\cup_{k=1}^{\infty}\mathcal{M}_{n}(k)$, then all
$\mathcal{M}_{n}$, as well as their union
$\cup_{n=1}^{\infty}\mathcal{M}_{n}$, are separable. This last union is the
set of all finite metric spaces, which, as noted in Example 6.27, is an
everywhere dense subset of $\mathcal{M}$, so that $\mathcal{M}$ is separable.
∎

Recall that a complete separable metric space is called _Polish_. Thus, the
following result holds.

######  Corollary 7.24.

The space $\mathcal{M}$ is Polish.

By Problem 1.31, for a metric space, the separability is equivalent to having
a countable base.

######  Corollary 7.25.

The space $\mathcal{M}$ has a countable base.

###  7.6 Calculating $\operatorname{mst}$-spectrum by means of
Gromov–Hausdorff distances

Recall that by $\Delta_{n}$ we denoted $n$-point metric space such that all
its nonzero distances equal $1$. Also, given $\lambda>0$ and any metric space
$X$, if we multiply by $\lambda$ all the distances in $X$, then the resulting
metric space we denote by $\lambda X$.

In the present section we show that the $\operatorname{mst}$-spectrum of an
arbitrary $n$-point metric space $X$ can be represented as a linear function
on the Gromov–Hausdorff distances from this space to the
$\lambda\Delta_{2},\ldots,\lambda\Delta_{n}$ for $\lambda\geq
2\operatorname{diam}X$.

######  Theorem 7.26.

Let $X$ be a finite metric space,
$\sigma(X)=(\sigma_{1},\ldots,\sigma_{n-1})$, $\lambda\geq
2\operatorname{diam}X$. Then

$\sigma_{k}=\lambda-2d_{GH}(\lambda\Delta_{k+1},X).$

###### Proof.

Choose any $1\leq k\leq n-1$ and arbitrary irreducible correspondence
$R\in\mathcal{R}^{0}(\lambda\Delta_{k+1},X)$. By Proposition 6.22, there
exists partitions $R_{\lambda\Delta_{k+1}}=\\{Z_{i}\\}_{i=1}^{p}$ and
$R_{X}=\\{X_{i}\\}_{i=1}^{p}$ of $\lambda\,\Delta_{k+1}$ and $X$,
respectively, such that $R=\cup_{i=1}^{p}Z_{i}\times X_{i}$, and
$\min\\{\\#Z_{i},\\#X_{i}\\}=1$ for all $i$. By Proposition 6.23, it holds
$\operatorname{dis}R\geq\max\\{\operatorname{diam}R_{\lambda\Delta_{k+1}},\operatorname{diam}R_{X}\\}$.
Thus, if for some $i$ we have $\\#Z_{i}>1$, then
$\operatorname{dis}R\geq\lambda\geq 2\operatorname{diam}X$. Since $k+1\leq n$,
there exists $R$ such that $\\#Z_{i}=1$ for all $i$. For such $R$, again by
Proposition 6.23, we have $\operatorname{dis}R\leq\operatorname{diam}X$.
Therefore,
$\inf_{R\in\mathcal{R}^{0}(\lambda\Delta_{k+1},X)}\operatorname{dis}R$ is
achieved on a correspondences of the latter type. The set of these
correspondences we denote by $\mathcal{R}$.

Now, if $R\in\mathcal{R}$, then $p=k+1$ and $R_{X}\in\mathcal{D}_{k+1}(X)$. By
Proposition 6.23, we have

$\operatorname{dis}R=\sup\bigl{\\{}\operatorname{diam}R_{X},\,|X_{i}X_{j}|^{\prime}-\lambda,\,\lambda-|X_{i}X_{j}|:1\leq
i<j\leq k+1\bigr{\\}}=\\\ =\sup\bigl{\\{}\lambda-|X_{i}X_{j}|:1\leq i<j\leq
k+1\bigr{\\}}=\lambda-\alpha(R_{X}),$

where the second equality holds because

$\max\bigl{\\{}|X_{i}X_{j}|^{\prime}-\lambda,\operatorname{diam}R_{X}\bigr{\\}}\leq\operatorname{diam}X\leq\lambda-\operatorname{diam}X\leq\lambda-|X_{i}X_{j}|$

for any $1\leq i<j\leq k+1$. Corollary 6.21, together with above
considerations, gives us

$2d_{GH}(\lambda\Delta_{k+1},X)=\min_{R\in\mathcal{R}}\operatorname{dis}R=\min_{R\in\mathcal{R}}\bigl{(}\lambda-\alpha(R_{X})\bigr{)}=\lambda-\max_{D\in\mathcal{D}_{k+1}(X)}\alpha(D),$

where the last equality holds because each $D$ generates some
$R\in\mathcal{R}$.

It remains to use Theorem 4.13 which states that

$\sigma_{k}=\max\bigl{\\{}\alpha(D):D\in\mathcal{D}_{k+1}(X)\bigr{\\}},$

thus, $2d_{GH}(\lambda\Delta_{k+1},X)=\lambda-\sigma_{k}$. ∎

######  Corollary 7.27.

Let $X$ be a finite metric space and $\lambda\geq 2\operatorname{diam}X$, then

$\operatorname{mst}X=\lambda(\\#X-1)-2\sum_{k=1}^{\\#X-1}d_{GH}(\lambda\Delta_{k+1},X).$

###  7.7 Steiner problem in Gromov–Hausdorff space

In this section we prove the following

######  Theorem 7.28.

Let $M\subset\mathcal{M}$ be a finite set such that each $X\in M$ is a finite
metric space. Then $\operatorname{SMT}(M,\mathcal{M})\neq\emptyset$, i.e., for
such $M$ the Steiner problem has a solution.

######  Remark 7.29.

For arbitrary finite $M\subset\mathcal{M}$ the problem is still open.

###### Proof.

Let $n=\\#M$. In Section 4.5 we introduced model full Steiner trees, and we
have shown how to use them for calculating the length of a Steiner minimal
tree. Recall the corresponding definitions in our case. A full Steiner tree
has the vertices of two types only: the ones of degree $1$ which we call
boundary, and the ones of degree $3$ which we call interior. In model full
Steiner trees which we use to treat the problem for such $M$, the vertex set
is $\\{1,\ldots,2n-2\\}$, where $\\{1,\ldots,n\\}$ are reserved for the
boundary vertices. We called two model full Steiner tree equivalent if there
is an isomorphism between them fixed on the boundary. By $\mathcal{B}_{n}$ we
denoted the set of all model full Steiner trees with $n$ boundary vertices
considered up to this equivalence.

Enumerate the points from $M$ in an arbitrary way, i.e., we consider a
bijection $\varphi\colon\\{1,\ldots,n\\}\to M$. Choose an arbitrary
$G\in\mathcal{B}_{n}$, and consider a network $\Gamma$ of the type $G$ for
which $\partial\Gamma=\varphi$. Then all such networks for given $G$ differ
from each other only in the “positions” of their interior vertices, thus the
set $[G,\varphi]$ of such networks can be identified with $\mathcal{M}^{n-2}$.
Then we proved (Corollary 4.24) that

$\operatorname{smt}(M,\mathcal{M})=\inf\bigl{\\{}|\Gamma|:\Gamma\in[G,\varphi],\,G\in\mathcal{B}_{n}\bigr{\\}}.$

Choose an arbitrary $G\in\mathcal{B}_{n}$ and any $\Gamma\in[G,\varphi]$. We
put $X_{i}=\Gamma(i)$, then $M=\\{X_{1},\ldots,X_{n}\\}$. For each $ij\in
E(G)$ we choose an arbitrary
$R_{ij}\in\mathcal{R}_{\operatorname{opt}}(X_{i},X_{j})$ in such a way that
$R_{ji}^{-1}=R_{ij}$. Let $X_{k}=\\{x_{k}^{i}\\}_{i=1}^{n_{k}}$, then for any
$k\in\\{1,\ldots,n\\}$ and any $1\leq i\leq n_{k}$ we construct a network
$\Gamma_{k}^{i}\colon\\{1,\ldots,2n-2\\}\to\sqcup_{j=1}^{2n-2}X_{j}$ as
follows: in each $X_{j}$ we choose one point
$x_{j}^{r_{j}}=:\Gamma_{k}^{i}(j)$ such that

  1. (1)

$x_{k}^{r_{k}}=x_{k}^{i}$;

  2. (2)

for any $pq\in E(G)$ we have $(x_{p}^{r_{p}},x_{q}^{r_{q}})\in R_{pq}$

(verify that it is always possible to do). Consider the set
$\mathcal{T}=\\{\Gamma_{k}^{i}\\}$ consisting of all $\Gamma_{k}^{i}$ over all
possible $k$ and $i$.

For any $j\in\\{1,\ldots,2n-2\\}$ we put
$V_{j}=\cup_{T\in\mathcal{T}}\\{T(j)\\}$, i.e., we gather in each $X_{j}$ all
points that are the images of the vertices of the constructed networks. Let us
note that all $V_{j}$ have at most $N:=\sum_{k=1}^{n}n_{k}$ points, and for
each $j\in\\{1,\ldots,n\\}$ it holds $V_{j}=X_{j}$.

Further, for each $p$ and $q$ such that $pq\in E(G)$ we denote by $R^{t}_{pq}$
the set of all pairs $(x_{p},x_{p})$ such that for some $T\in\mathcal{T}$ we
have $x_{p}=T(p)$ and $x_{q}=T(q)$, i.e., we gather all pairs forming the
images of the edges of the constructed networks. Thus, we obtained
correspondences $R^{t}_{pq}\in\mathcal{R}(V_{p},V_{q})$ such that
$R^{t}_{pq}\subset R_{pq}$, hence

$d_{GH}(V_{p},V_{q})\leq\operatorname{dis}R^{t}_{pq}\leq\operatorname{dis}R_{pq}=d_{GH}(X_{p},X_{q}).$

Denote by $\Gamma^{t}$ the network $\Gamma^{t}\colon p\mapsto V_{p}$. Since
$\Gamma^{t}|_{\\{1,\ldots,n\\}}=\varphi$ and $\Gamma^{t}$ has the type $G$,
then $\Gamma^{t}\in[G,\varphi]$. Denote by $[G,\varphi]^{t}$ the set of all
such $\Gamma^{t}$. Since $|\Gamma^{t}|\leq|\Gamma|$, then

$\operatorname{smt}(M,\mathcal{M})=\inf\bigl{\\{}|\Gamma^{t}|:\Gamma^{t}\in[G,\varphi]^{t},\,G\in\mathcal{B}_{n}\bigr{\\}}.$

However, all $X_{i}$ belong to $\mathcal{M}_{N}$, therefore,
$\operatorname{smt}(M,\mathcal{M})=\operatorname{smt}(M,\mathcal{M}_{N})$.
Moreover, if we choose $\Gamma^{t}$ such that all $V_{i}$, $i\geq n+1$,
coincide with $V_{k}$ for some $k\leq n$, then
$\operatorname{smt}(M,\mathcal{M}_{N})\leq\sum_{1\leq p,q\leq
n}d_{GH}(X_{p},X_{q})=:D^{\prime}$. Thus, it suffices to consider only
$\Gamma^{t}$ with $|\Gamma^{t}|\leq D^{\prime}$, in particular, for such
$\Gamma^{t}$ and any $pq\in E(G)$ we have $d_{GH}(V_{p},V_{q})\leq
D^{\prime}$.

Let us put $d=\max\\{\operatorname{diam}X_{k}:k=1,\ldots,n\\}$. Since for any
$X,Y\in\mathcal{M}$ we have
$d_{GH}(X,Y)\geq\frac{1}{2}|\operatorname{diam}X-\operatorname{diam}Y|$, then
for each $X_{p}$ we have $\operatorname{diam}X_{p}\leq d+2(n-2)D^{\prime}=:D$
(all these estimates are rather rough, however, we do not need exact ones
here). In account, we proved that all $X_{p}$ belongs to $\mathcal{M}_{N}(D)$.
By Problem 7.4, the space $\mathcal{M}_{N}(D)$ is compact, that is why the
continuous function $\ell\colon\mathcal{M}_{N}(D)^{n-2}\to\mathbb{R}$,
$\ell\colon(X_{n+1},\ldots,X_{2n-2})\mapsto|\Gamma^{t}|$, attains its minimum
at some $\Gamma^{t}_{0}$. It remains to notice that $\mathcal{B}_{n}$ is
finite. ∎

## References to Chapter 7

  * [1] Burago D., Burago Yu., Ivanov S. _A Course in Metric Geometry_. Graduate Studies in Mathematics, vol.33, A.M.S., Providence, RI, 2001.

### Exercises to Chapter 7

######  Exercise 7.1.

Prove that the product topology on $X\times Y$ coincides with the one
generated by the metric from Agreement 7.1.

######  Exercise 7.2.

Prove that the topologies generated by all $d_{t}$, and by $|\cdot|$ as well,
coincide with the product topology of $X\times Y$.

######  Exercise 7.3.

Prove that

  1. (1)

a metric space $X$ is bounded if only for some $\varepsilon>0$ it holds
$\operatorname{cov}(X,\varepsilon)<\infty$ (similarly,
$\operatorname{pack}(X,\varepsilon)<\infty$);

  2. (2)

a metric space $X$ is finite if and only if there exists $n$ such that
$\operatorname{cov}(X,\varepsilon)\leq n$ for all $\varepsilon>0$ (similarly,
for $\operatorname{pack}(X,\varepsilon)$);

  3. (3)

the functions $f(\varepsilon)=\operatorname{cov}(X,\varepsilon)$ and
$g(\varepsilon)=\operatorname{pack}(X,\varepsilon)$ are monotonically
decreasing.

######  Exercise 7.4.

Prove that the set $\mathcal{M}_{n}(D)$ is compact, while
$\mathcal{M}_{[n]}(D)$ for $n>1$ is not.

##  Chapter 8 Calculating GH-distances to simplexes and some applications.

  * Schedule.

GH-distance to simplexes with more points, GH-distance to simplexes with at
most the same number of points, generalized Borsuk problem, solution of
generalized Borsuk problem in terms of GH-distances, clique covering number
and chromatic number of simple graphs, their dualities, calculating these
numbers in terms of GH-distances.

By _simplex_ we mean a metric space in which all non-zero distances equal to
each other. If $m$ is an arbitrary cardinal number, a simplex contain $m$
points, and all its non-zero distances equal $1$, then we denote this simplex
by $\Delta_{m}$. Thus, $\lambda\Delta_{m}$, $\lambda>0$, is a simplex whose
non-zero distances equal $\lambda$. Also, for arbitrary metric space $X$ and
$\lambda=0$, the space $\lambda X$ coincides with $\Delta_{1}$.

###  8.1 Gromov–Hausdorff distance to simplexes with more points

The next result generalizes Theorem 4.1 from [1].

######  Theorem 8.1.

Let $X$ be an arbitrary metric space, $m>\\#X$ a cardinal number, and
$\lambda\geq 0$, then

$2d_{GH}(\lambda\Delta_{m},X)=\max\\{\lambda,\operatorname{diam}X-\lambda\\}.$

###### Proof.

If $X$ is unbounded, then $2d_{GH}(\lambda\Delta_{m},X)=\infty$ by Example
6.29, and we get what is required.

Now, let $\operatorname{diam}X<\infty$.

If $\\#X=1$, then $\operatorname{diam}X=0$, and, by Example 6.28, we have

$2d_{GH}(\lambda\Delta,X)=\operatorname{diam}\lambda\Delta=\lambda=\max\\{\lambda,\operatorname{diam}X-\lambda\\}.$

If $\lambda=0$, then, by Example 6.28, we have

$2d_{GH}(\Delta_{1},X)=\operatorname{diam}X=\max\\{\lambda,\operatorname{diam}X-\lambda\\}.$

Let $\\#X>1$ and $\lambda>0$. Choose an arbitrary
$R\in\mathcal{R}(\lambda\Delta_{m},X)$. Since $\\#X<m$ and $\lambda>0$, then
there exists $x\in X$ such that $\\#R^{-1}(x)\geq 2$, thus,
$\operatorname{dis}R\geq\lambda$ and
$2d_{GH}(\lambda\Delta_{m},X)\geq\lambda$.

Consider an arbitrary sequence $(x_{i},y_{i})\in X\times X$ such that
$|x_{i}y_{i}|\to\operatorname{diam}X$. If it contains a subsequence
$(x_{i_{k}},y_{i_{k}})$ such that for each $i_{k}$ there exists
$z_{k}\in\lambda\Delta$, $(z_{k},x_{i_{k}})\in R$, $(z_{k},y_{i_{k}})\in R$,
then $\operatorname{dis}R\geq\operatorname{diam}X$ and

$2d_{GH}(\lambda\Delta_{m},X)\geq\max\\{\lambda,\operatorname{diam}X\\}\geq\max\\{\lambda,\operatorname{diam}X-\lambda\\}.$

If such subsequence does not exist, then there exists a subsequence
$(x_{i_{k}},y_{i_{k}})$ such that for any $i_{k}$ there exist distinct
$z_{k},w_{k}\in\lambda\Delta_{m}$, $(z_{k},x_{i_{k}})\in R$,
$(w_{k},y_{i_{k}})\in R$, and, therefore,

$2d_{GH}(\lambda\Delta_{m},X)\geq\max\bigl{\\{}\lambda,|\operatorname{diam}X-\lambda|\bigr{\\}}\geq\max\\{\lambda,\operatorname{diam}X-\lambda\\}.$

Thus, in the both cases we have
$2d_{GH}(\lambda\Delta,X)\geq\max\bigl{\\{}\lambda,\operatorname{diam}X-\lambda\bigr{\\}}$.

Choose an arbitrary $x_{0}\in X$, then, by assumption, $\\#X>1$, and, thus,
the set $X\setminus\\{x_{0}\\}$ is not empty. Since $\\#X<m$, then
$\lambda\Delta_{m}$ contains a subset $\lambda\Delta^{\prime}$ of the same
cardinality with $X\setminus\\{x_{0}\\}$. Let
$g\colon\lambda\Delta^{\prime}\to X\setminus\\{x_{0}\\}$ be an arbitrary
bijection, and
$\lambda\Delta^{\prime\prime}=\lambda\Delta_{m}\setminus\lambda\Delta^{\prime}$,
then $\\#\lambda\Delta^{\prime\prime}>1$. Consider the following
correspondence:

$R_{0}=\Bigl{\\{}\bigl{(}z^{\prime},g(z^{\prime})\bigr{)}:z^{\prime}\in\lambda\Delta^{\prime}\Bigr{\\}}\cup\bigl{(}\lambda\Delta^{\prime\prime}\times\\{x_{0}\\}\bigr{)}.$

Then we can apply Proposition 6.23, thus we have

$\operatorname{dis}R_{0}=\sup\\{\lambda,|x_{1}x^{\prime}_{1}|-\lambda,\lambda-|x_{2}x^{\prime}_{2}|:x_{1},x^{\prime}_{1},x_{2},x^{\prime}_{2}\in
X,\,x_{1}\neq x^{\prime}_{1},\,x_{2}\neq
x^{\prime}_{2}\\}=\max\\{\lambda,\operatorname{diam}X-\lambda\\},$

therefore,

$2d_{GH}(\lambda\Delta,X)=\max\\{\lambda,\operatorname{diam}X-\lambda\\},$

what is required. ∎

###  8.2 Gromov–Hausdorff distance to simplexes with at most the same number
of points

Let $X$ be an arbitrary set different from singleton, $2\leq m\leq\\#X$ a
cardinal number, and $\lambda>0$. Under notations from Section 6.1, consider
an arbitrary $D\in\mathcal{D}_{m}(X)$, any bijection
$g\colon\lambda\Delta_{m}\to D$, and construct the correspondence
$R_{D}\in\mathcal{R}(\lambda\Delta_{m},X)$ in the following way:

$R_{D}=\bigcup_{z\in\lambda\Delta_{m}}\\{z\\}\times g(z).$

Clearly that each correspondence $R_{D}$ is irreducible.

From Proposition 6.23 we get

######  Proposition 8.2.

Let $X\neq\Delta_{1}$ be an arbitrary metric space, $2\leq m\leq\\#X$ a
cardinal number, and $\lambda>0$. Then for any $D\in\mathcal{D}_{m}(X)$ it
holds

$\operatorname{dis}R_{D}=\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\beta(D)-\lambda\\}.$

###### Proof.

If $X$ is unbounded, then $\operatorname{dis}R=\infty$ for any
$R\in\mathcal{R}(\lambda\Delta_{m},X)$. Since $m\geq 2$, for any
$D=\\{X_{i}\\}_{i\in I}\in\mathcal{D}_{m}(X)$ we have either
$\operatorname{diam}D=\infty$, or $\beta(D)=\infty$. Indeed, if
$\operatorname{diam}D<\infty$ and $\beta(D)<\infty$ then for any $x,y\in X$
either $x,y\in X_{i}$, thus $|xy|\leq\operatorname{diam}D$, or $x\in X_{i}$,
$y\in X_{j}$, $i\neq j$, and $|xy|\leq|X_{i}X_{j}|\leq\beta(D)$, therefore $X$
is bounded. Thus, for unbounded $X$ the right-hand side of the considered
equation is infinite as well, thus we get what is required.

Now, let $\operatorname{diam}X<\infty$. By Proposition 6.23, we have

$\operatorname{dis}R_{D}=\sup\bigl{\\{}\operatorname{diam}D,\,\lambda-|X_{i}X_{j}|,\,|X_{i}X_{j}|^{\prime}-\lambda:i,j\in
I,\,i\neq
j\bigr{\\}}=\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\beta(D)-\lambda\\},$

that completes the proof. ∎

######  Corollary 8.3.

Let $X\neq\Delta_{1}$ be an arbitrary metric space, $2\leq m\leq\\#X$ a
cardinal number, and $\lambda>0$. Then for any $D\in\mathcal{D}_{m}(X)$ it
holds

$\operatorname{dis}R_{D}=\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\operatorname{diam}X-\lambda\\}.$

###### Proof.

Again, for unbounded $X$ the equation evidently holds.

Consider now the case of bounded $X$. Notice that
$\operatorname{diam}D\leq\operatorname{diam}X$ and
$\beta(D)\leq\operatorname{diam}X$. In addition, if
$\operatorname{diam}D<\operatorname{diam}X$, and $(x_{i},y_{i})\in X\times X$
is a sequence such that $|x_{i}y_{i}|\to\operatorname{diam}X$, then, starting
from some $i$, the points $x_{i}$ and $y_{i}$ belong to different elements of
$D$, therefore, in this case we have $\beta(D)=\operatorname{diam}X$, and the
formula is proved.

Now, let $\operatorname{diam}D=\operatorname{diam}X$, then
$\beta(D)-\lambda\leq\operatorname{diam}X$ and
$\operatorname{diam}X-\lambda\leq\operatorname{diam}X$, thus

$\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\beta(D)-\lambda\\}=\max\\{\operatorname{diam}X,\,\lambda-\alpha(D)\\}=\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\operatorname{diam}X-\lambda\\},$

that completes the proof. ∎

######  Proposition 8.4.

Let $X\neq\Delta_{1}$ be an arbitrary metric space, and $2\leq m\leq\\#X$ a
cardinal number, and $\lambda>0$. Then

$2d_{GH}(\lambda\Delta_{m},X)=\inf_{D\in\mathcal{D}_{m}(X)}\operatorname{dis}R_{D}.$

###### Proof.

The case of unbounded $X$ is trivial, so, let $X$ be bounded. By Corollary
6.21,

$2d_{GH}(\lambda\Delta_{m},X)=\inf_{R\in\mathcal{R}^{0}(\lambda\Delta_{m},X)}\operatorname{dis}R,$

thus it suffices to prove that for any irreducible correspondence
$R\in\mathcal{R}^{0}(\lambda\Delta_{m},X)$ there exists
$D\in\mathcal{D}_{m}(X)$ such that
$\operatorname{dis}R_{D}\leq\operatorname{dis}R$.

Let us choose an arbitrary $R\in\mathcal{R}^{0}(\lambda\Delta_{m},X)$ such
that it cannot be represented in the form $R_{D}$, then the partition
$D^{R}_{\lambda\Delta_{m}}$ is not pointwise, i.e., there exists $x\in X$ such
that $\\#R^{-1}(x)\geq 2$, therefore, $\operatorname{dis}R\geq\lambda$.

Define a metric on the set $D^{R}_{\lambda\Delta_{m}}$ to be equal $\lambda$
between any its distinct elements, then this metric space is isometric to a
simplex $\lambda\Delta^{\prime}_{n}$, $n\leq m$. The correspondence $R$
generates naturally another correspondence
$R^{\prime}\in\mathcal{R}(\lambda\Delta^{\prime}_{n},X)$, namely, if
$D^{R}_{\lambda\Delta_{m}}=\\{\Delta_{j}\\}_{j\in J}$, and $f_{R}\colon
D^{R}_{\lambda\Delta_{m}}\to D^{R}_{X}$ is the bijection generated by $R$,
then

$R^{\prime}=\bigcup_{j\in J}\\{\Delta_{j}\\}\times f_{R}(\Delta_{j}).$

It is easy to see that
$\operatorname{dis}R=\max\\{\lambda,\,\operatorname{dis}R^{\prime}\\}$.
Moreover, $R^{\prime}$ is generated by the partition $D^{\prime}=D^{R}_{X}$,
i.e., $R^{\prime}=R_{D^{\prime}}$, thus, by Corollary 8.3, we have

$\operatorname{dis}R^{\prime}=\max\\{\operatorname{diam}D^{\prime},\,\lambda-\alpha(D^{\prime}),\,\operatorname{diam}X-\lambda\\},$

and hence,

$\operatorname{dis}R=\max\\{\lambda,\operatorname{diam}D^{\prime},\,\lambda-\alpha(D^{\prime}),\,\operatorname{diam}X-\lambda\\}=\max\\{\lambda,\,\operatorname{diam}D^{\prime},\,\operatorname{diam}X-\lambda\\}.$

Since $n\leq m$, the partition $D^{\prime}$ has a subpartition
$D\in\mathcal{D}_{m}(X)$. Clearly,
$\operatorname{diam}D\leq\operatorname{diam}D^{\prime}$, therefore,

$\operatorname{dis}R_{D}=\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\operatorname{diam}X-\lambda\\}\leq\max\\{\operatorname{diam}D^{\prime},\,\lambda,\,\operatorname{diam}X-\lambda\\}=\operatorname{dis}R,$

q.e.d. ∎

Considering separately the case $\lambda=0$, we get the following

######  Corollary 8.5.

Let $X\neq\Delta_{1}$ be an arbitrary metric space, $2\leq m\leq\\#X$ a
cardinal number, and $\lambda\geq 0$. Then

$2d_{GH}(\lambda\Delta_{m},X)=\inf_{D\in\mathcal{D}_{m}(X)}\max\\{\operatorname{diam}D,\,\lambda-\alpha(D),\,\operatorname{diam}X-\lambda\\}.$

For any metric space $X$ put

$\varepsilon(X)=\inf\bigl{\\{}|xy|:x,y\in X,\,x\neq y\bigr{\\}}.$

Notice that $\varepsilon(X)\leq\operatorname{diam}X$, and for a bounded $X$
the equality holds, if and only if $X$ is a simplex.

Corollary 8.5 immediately implies the following result that is proved in [1].

######  Theorem 8.6 ([1]).

Let $X\neq\Delta_{1}$ be a finite metric space, $m=\\#X$, and $\lambda\geq 0$,
then

$2d_{GH}(\lambda\Delta_{m},X)=\max\bigl{\\{}\lambda-\varepsilon(X),\,\operatorname{diam}X-\lambda\bigr{\\}}.$

###  8.3 Generalized Borsuk problem

Classical Borsuk Problem deals with partitions of subsets of Euclidean space
into parts having smaller diameters. We generalize the Borsuk problem to
arbitrary bounded metric spaces and partitions of arbitrary cardinality. Let
$X$ be a bounded metric space, $m$ a cardinal number such that $2\leq
m\leq\\#X$, and $D=\\{X_{i}\\}_{i\in I}\in\mathcal{D}_{m}(X)$. We say that $D$
is a partition into subsets having _strictly smaller diameters_ , if there
exists $\varepsilon>0$ such that
$\operatorname{diam}X_{i}\leq\operatorname{diam}X-\varepsilon$ for all $i\in
I$.

By _Generalized Borsuk problem_ we call the following one: Is it possible to
partition a bounded metric space $X$ into a given, probably infinite, number
of subsets, each of which has a strictly smaller diameter than $X$?

We give a solution to the Generalized Borsuk problem in terms of the
Gromov–Hausdorff distance.

######  Theorem 8.7.

Let $X$ be an arbitrary bounded metric space and $m$ a cardinal number such
that $2\leq m\leq\\#X$. Choose an arbitrary number
$0<\lambda<\operatorname{diam}X$, then $X$ can be partitioned into $m$ subsets
having strictly smaller diameters if and only if
$2d_{GH}(\lambda\Delta_{m},X)<\operatorname{diam}X$.

###### Proof.

For the $\lambda$ chosen, due Corollary 8.5, we have
$2d_{GH}(\lambda\Delta_{m},X)\leq\operatorname{diam}X$, and the equality holds
if and only if for each $D\in\mathcal{D}_{m}(X)$ we have
$\operatorname{diam}D=\operatorname{diam}X$. The latter means that there is no
partition of the space $X$ into $m$ parts having strictly smaller diameters. ∎

######  Corollary 8.8.

Let $d>0$ be a real number, and $m\leq n$ cardinal numbers. By
$\mathcal{M}_{n}$ we denote the set of isometry classes of bounded metric