26
$\begingroup$

This is a purely idle question, which emerged during a conversation with a friend about what is (not) known about the space of compact metric spaces. I originally asked this question at math.stackexchange (https://math.stackexchange.com/questions/1356066/global-structure-of-the-gromov-hausdorff-space), but received no answers even after bountying.

Background. If $A, B$ are compact subsets of a metric space $M$, the Hausdorff distance between $A$ and $B$ is the worst worst best distance between their points: $$d_H(A, B)=\max\{\sup\{\inf\{d(a, b): b\in B\}: a\in A\}, \sup\{\inf\{d(a, b): a\in A\}: b\in B\}\}.$$ For two compact metric spcaes $X, Y$, their Gromov-Hausdorff distance is the infimum (in fact, minimum) over all isometric embeddings of $X, Y$ into $Z$ via $f, g$ of $d_H(f(X), g(Y))$. The Gromov-Hausdorff space $\mathcal{GH}$ is then the "set" of isometry classes of compact metric spaces, with the metric $d_{GH}$.)

Question. How homogeneous is $\mathcal{GH}$? For example: while distinct points in $\mathcal{GH}$ are in fact distinguishable in a broad sense, it's not clear that distinct points can always be distinguished just by the metric structure of $\mathcal{GH}$, so it's reasonable to ask:

Are there any nontrivial self-isometries of $\mathcal{GH}$?

There are of course lots of related questions one can ask (e.g., autohomeomorphisms instead of isometries); I'm happy for any information about the homogeneity of $\mathcal{GH}$.


Please feel free to add tags if more are appropriate.

$\endgroup$
9
  • 3
    $\begingroup$ For any $r>0$, there is an autohomeomorphism of $\mathcal{GH}$ that takes a compact metric space and scales its metric by $r$. $\endgroup$ Jul 26, 2015 at 19:46
  • $\begingroup$ On the first place: does $d_{GH}$ behaves as a distance? does it satisfy the triangle inequality? is $d(X,Y)>0$ whenever $X,Y$ are non-isometric? (Btw, the Hausdorff distance is for non-empty compact subsets, and hence $d_{GH}$ is also for non-empty compact metric spaces only.) $\endgroup$
    – YCor
    Jul 26, 2015 at 20:50
  • $\begingroup$ @EricWofsey yes, for autohomeomorphisms the question should be about (anything approaching a) classification rather than existence. $\endgroup$ Jul 26, 2015 at 22:55
  • 4
    $\begingroup$ @YCor I assume all metric spaces are nonempty as a rule :). Yes, $d_{GH}$ (restricted to the compact spaces!) is a metric, and in particular satisfies the triangle inequality; see e.g. helsinki.fi/~cristina/pdfs/gromovHausdorff.pdf $\endgroup$ Jul 26, 2015 at 22:57
  • 4
    $\begingroup$ @YCor: That the space GH is geodesic is proved in arxiv.org/abs/1504.03830. The question of whether GH is homeomorphic to $\ell^2$ is Problem 1062 in [T.Banakh, R.Cauty, M.Zarichnyi, Open problems in infinite-dimensional topology. in: Open Problems in Topology, II (E.Pearl ed.), Elsevier, 2007, p.601–624] electronically available at franko.lviv.ua/faculty/mechmat/Departments/Topology/…. $\endgroup$ Jul 30, 2015 at 10:57

2 Answers 2

23
$\begingroup$

To answer the main question -- there are no nontrivial self-isometries of $\mathcal{GH}$.

I can give a proof of this, but as it is getting rather long, I will state some facts in $\mathcal{GH}$ without proof for now, and will come back and provide provide proofs or references.

First, a bit of notation. Let ${\rm diam}(A)=\sup\{d(a,b)\colon a,b\in A\}$ denote the diameter of a metric space $A$. For any $\lambda > 0$ use $\lambda A$ to denote the space with the same points as $A$, but with scaled metric given by $d_\lambda(a,b)=\lambda d(a,b)$. Let $\Delta_n$ denote the (n-1)-simplex - a space consisting of $n$ points all at unit distance from each other. So, $\Delta_1$ is the space consisting of a single point, and $\lambda\Delta_n$ is a space consisting of $n$ points all at distance $\lambda$ from each other.

Now, the following are standard, \begin{align} &d_{GH}(\Delta_1,A)=\frac12{\rm diam}(A),\\ &d_{GH}(A,B)\le\frac12\max({\rm diam}(A),{\rm diam}(B)),\\ &d_{GH}(\lambda A,\mu A)=\frac12\lvert\lambda-\mu\rvert{\rm diam}(A). \end{align} For reference, I am using Some Properties of Gromov–Hausdorff Distances by Fecundo Mémoli for the standard properties of $\mathcal{GH}$. Then, the one-point space $\Delta_1$ is distinguished just in terms of the metric on $\mathcal{GH}$ as follows,

1. $A$ is isometric to $\Delta_1$ if and only if $d_{GH}(B,C)\le\max(d_{GH}(A,B),d_{GH}(A,C))$ for all $B,C\in\mathcal{GH}$.

That this inequality holds for $A=\Delta_1$ follows from the first two standard properties above. On the other hand, if $A$ contains more than one point, so ${\rm diam}(A)>0$, we can take $B=\Delta_1$ and $C=\lambda A$ for any $\lambda > 1$, $$ \begin{eqnarray} d_{GH}(B,C)&=&d_{GH}(\Delta_1,\lambda A)=\frac\lambda2{\rm diam}(A) \\ &>&\frac12\max(1,\lambda-1){\rm diam}(A)=\max(d_{GH}(A,B),d_{GH}(A,C)) \end{eqnarray}. $$ So, statement 1 holds in both directions. Therefore, any isometry fixes $\Delta_1$ and, by the first standard property of $\mathcal{GH}$ above, it preserves the diameter of spaces.

Next, the simplexes $\Delta_n$ are distinguished in terms of the metric as follows,

2. The following are equivalent for any $A\in\mathcal{GH}$.

  • ${\rm diam}(A)=1$ and $d_{GH}(B,C)\le\max(d_{GH}(A,B),d_{GH}(A,C))$ for all $B,C\in\mathcal{GH}$ with diameter less than or equal to $1$.
  • $A=\Delta_n$ for some $n\ge2$.

The proof of this is given below. So, an $\iota$ is an isometry on $\mathcal{GH}$ maps the set of simplifies $\{\Delta_n\colon n\ge2\}$ to itself. Now, the finite spaces in $\mathcal{GH}$ can be identified.

3. For any $n\ge2$ and $A\in\mathcal{GH}$, the following are equivalent.

  • $d_{GH}(A,B)=d_{GH}(\Delta_n,B)$ for all $B\in\mathcal{GH}$ with $d_{GH}(\Delta_n,B)={\rm diag}(B)\ge\max({\rm diag}(A),1)$.
  • $A$ is a finite space $n$ or fewer points.

Therefore, if $\mathcal{GH}_n$ denotes the finite metric spaces with $n$ or fewer points, (2) and (3) imply that $\iota$ permutes $\{\mathcal{GH}_n\colon n\ge2\}$. As it must preserve the inclusions $\mathcal{GH}_n\subset\mathcal{GH}_{n+1}$, it follows that $\iota$ maps $\mathcal{GH}_n$ to itself for each $n\ge2$.

Now, fix $n\ge2$, let $N=n(n-1)/2$, and $S$ be the subset of $\mathbb{R}^N$ consisting of points $\mathbf x=(x_{ij})_{1\le i < j\le n}$ with $x_{ij}>0$ and $x_{ik}\le x_{ij}+x_{jk}$ for all distinct $i,j$ (here, I am using $x_{ij}\equiv x_{ji}$ whenever $i > j$. Let $G$ be the group of linear transformations of $\mathbb{R}^N$ mapping $\mathbf x$ to $g_ \sigma(\mathbf x)=(x_{\sigma(i)\sigma(j)})$ for permutations $\sigma\in S_n$. Then, $S$ is a region in $\mathbb{R}^N$ with nonempty interior bounded by a finite set of hyperplanes, and maps in $G$ take the interior of $S$ into itself. We can define $\theta\colon S\to\mathcal{GH}$ by letting $\theta(\mathbf x)$ be the space with $n$ points $a_1,\ldots,a_n$ and $d(a_i,a_j)=x_{ij}$, and define a (continuous multivalued) function $f\colon S\to S$ by $\theta\circ f=\iota\circ\theta$. Then, $\theta$ maps $S$ onto the metric spaces with $n$ points, the values of $f(\mathbf x)$ are orbits of $G$, and the fact that $\iota$ is an isometry means that if $\mathbf y=f(\mathbf x)$ and $\mathbf y^\prime=f(\mathbf x^\prime)$, then $\min_g\lVert g(\mathbf y)-\mathbf y^\prime\rVert=\min_g\lVert g(\mathbf x)-\mathbf x^\prime\rVert$, with the minimum taken over $g\in G$ and using the $\ell_\infty$ norm on $\mathbb{R}^N$.

Now, let $X\subset\mathbb{R}^N$ consist of the fixed points of elements of $G$, which is a finite union of hyperplanes, and $S^\prime=S\setminus\ X$. Note that $f$ maps $S^\prime$ into itself -- suppose that $\mathbf y = f(\mathbf x)\in X$ for some $\mathbf x\in S^\prime$. Then, $g(\mathbf y)=\mathbf y$ for some $g\in G$. Choosing $f(\mathbf x^\prime)=\mathbf y^\prime$ arbitrarily close to $\mathbf y$ with $h(\mathbf y^\prime)\not=\mathbf y^\prime$ (all $h\in G$), we have $\mathbf x^\prime$ and and $g(\mathbf x^\prime)$ arbitrarily close to $\mathbf x$, so $g(\mathbf x)=\mathbf x$, contradicting the assumption. So, in the neighbourhood of any point in $S^\prime$, we can take a continuous branch of $f$, in which case $f$ is locally an isometry under the $\ell_\infty$ norm, which is only the case if $f(\mathbf x)=P\mathbf x+\mathbf b$ (where $P$ permutes and possibly flips the signs of elements of $\mathbf x$, and $\mathbf b\in\mathbb{R}^N$), with $P$ and $\mathbf b$ constant over each component of $S^\prime$. As $\mathbf x\to 0$, $\theta(\mathbf x)$ tends to $\Delta_1$, from which we see that $\mathbf b=0$.

So, we have $f(\mathbf x)=P\mathbf x$, and as the components of $f(\mathbf x)$ are positive, $P$ is a permutation matrix. In order that $f$ is continuous across the hyperplanes in $X$, we see that $P$ is constant over all of $S^\prime$ (choosing continuous branches of $f$ across each hyperplane). Then, $P^{-1}gP\in G$, for all $g\in G$, as $f$ is invariant under the action of $G$. So, $P$ is in the normalizer of $G$. Now, it can be seen that centraliser of $G$ in the group of permutations (acting on $\mathbb{R}^N$ by permuting the elements) is trivial, which implies that its normaliser is itself (Permutation Groups, see the comment preceding Theorem 4.2B). Hence $P\in G$, so $\iota$ acts trivially on the spaces with $n$ points. As the finite spaces are dense in $\mathcal{GH}$, $\iota$ is trivial.


I'll now give a proof of statement (2) above, for which the following alternative formulation of the Gromov-Hausdorff distance will be useful. A correspondence, $R$, between two sets $A$ and $B$ is a subset of $A\times B$ such that, for each $a\in A$ there exists $b\in B$ such that $(a,b)\in R$ and, for each $b\in B$, there is an $a\in A$ with $(a,b)\in R$. The set of correspondences between $A$ and $B$ is denoted by $\mathcal R(A,B)$. If $A,B$ are metric spaces then the discrepancy of $R$ is, $$ {\rm dis}(R)=\sup\left\{\lvert d(a_1,a_2)-d(b_1,b_2)\rvert\colon (a_1,b_1),(a_2,b_2)\in R\right\}. $$ The Gromov-Hausdorff distance is the infimum of ${\rm dis}(R)/2$ taken over $R\in\mathcal R(A,B)$.

Now, lets prove (2), starting with the case where $A=\Delta_n$, some $n\ge2$, for which we need to prove $$ d_{GH}(B,C)\le\max(d_{GH}(\Delta_n,B),d_{GH}(\Delta_n,C)) $$ whenever $B,C$ have diameter bounded by $1$. As we have, $d_{GH}(B,C)\le1/2$, the required inequality is trivial unless $d_{GH}(\Delta_n,B)$ and $d_{GH}(\Delta_n,C)$ are strictly less than $1/2$, so we suppose that this is the case. Denote the points of $\Delta_n$ by $p_1,p_2,\ldots,p_n$. If $R\in\mathcal R(\Delta_n,B)$ is such that ${\rm dis}(R)/2 < 1/2$, then letting $B_i$ consist of the points $b\in B$ with $(p_i,b)\in R$, the sets $B_1,\ldots,B_n$ cover $B$. For any $b,b^\prime\in B_i$ then $d(b,b^\prime)=\lvert d(p_i,p_i)-d(b,b^\prime)\rvert\le{\rm dis}(R)$, so the $B_i$ have diameters bounded by ${\rm dis}(R)$. Also, for any $i\not=j$, if $b\in B_i\cap B_j$ then ${\rm dis}(R)\ge\lvert d(p_i,p_j)-d(b,b)\rvert=1$, giving a contradiction. So, the $B_i$ are disjoint sets covering $B$. Similarly, if $S\in\mathcal R(\Delta_n,C)$ has ${\rm dis}(S)/2 < 1/2$ then we can partition $C$ into $n$ sets, $C_i$, of diameter bounded by ${\rm dis}(S)$. Defining $T=\bigcup_{i=1}^n(B_i\times C_i)\in\mathcal R(B,C)$, it can be seen that ${\rm dis}(T)\le\max({\rm dis}(R),{\rm dis}(S))$, from which the required inequality follows.

Now, we prove the converse - if $A$ has diameter $1$ and is not isometric to $\Delta_n$ for any $n$, then we can find spaces $B,C$ of diameter $1$ with $d_{GH}(B,C)=1/2$ and with $d_{GH}(A,B)$, $d_{GH}(A,C)$ strictly less than $1/2$. I'll consider first the case where $A$ is finite with $m\ge2$ points, so $A=\{a_1,\ldots,a_m\}$. As $A$ is not isometric to $\Delta_m$, there must exist two points separated by less than unit distance. Wlog, take $d(a_{m-1},a_m)=x < 1$. Then, $m > 2$, otherwise $A$ would have diameter $x < 1$. We can define $R\in\mathcal R(A,\Delta_{m-1})$ to be $\{(a_i,p_i)\colon i=1,\ldots,m-1\}\cup\{(a_m,p_{m-1})\}$, which has discrepancy bounded by the max of $\lvert d(a_i,a_j)-1\rvert$ over $i\not=j$ and $d(a_{m-1},a)m)=x$. So, $d_{GH}(A,\Delta_{m-1}) < 1/2$. Next, we can define $R\in\mathcal R(A,\Delta_m)$ to be the collection of pairs $(a_i,p_i)$ for $i=1,\ldots,m$. Its discrepancy is the max of $d(a_i,a_j)-1$ over $i\not=j$, which is strictly less than $1$, so $d_{GH}(A,\Delta_m) < 1/2$. However, $d_{GH}(\Delta_{m-1},\Delta_m)=1/2$, so $B=\Delta_{m-1}$ and $C=\Delta_m$ satisfies the desired properties.

Now, suppose that $A$ is not a finite space. For any $m\ge2$ there exists a collection $a_1,a_2,\ldots,a_m$ of $m$ distinct points in $A$. Then, by compactness, we can cover $A$ with a finite collection of nonempty sets $A_1,\ldots,A_r$ of diameter bounded by $1/2$. Set $A_{r+i}=\{a_i\}$ for $i=1,\ldots,m$. Let $S=\{s_1,\ldots,s_{m+r}\}$ be the finite space with $d(s_i,s_j)=1$ for $i,j > r$ and with distance $1/2$ between all other pairs of points. The correspondence $R=\bigcup_{i=1}^{m+r}(A_i\times\{s_i\})$ has discrepancy $$ {\rm dis}(R)=\max\left\{1/2,1-d(a_i,a_j)\colon 1\le i < j\le m\right\} < 1. $$ So, $S$ is finite with diameter $1$, contains a subset isometric to $\Delta_m$, and $d_{GH}(A,S) < 1/2$.

Now, we can let $B$ be any finite set with diameter $1$ and $d_{GH}(A,B) < 1/2$. If $m$ greater than the number of points in $B$, let $C$ be a finite set with diameter $1$, a subset isometric to $\Delta_m$, and $d_{GH}(A,C) < 1/2$. Then, $d_{GH}(B,C)=1/2$, and satisfies the required properties, proving (2).

$\endgroup$
2
  • 1
    $\begingroup$ I'll come back and add the proofs of (2) and (3) when I have some time. $\endgroup$ Aug 5, 2015 at 1:03
  • $\begingroup$ Lets consider the map $\phi$ on $\mathcal{GH}$ with $\phi(X)=$The hyperspace of $X$. However it is not surjective but I wonder if this is an isometry? $\endgroup$ Jun 13, 2018 at 10:37
11
$\begingroup$

We have written a text with more details on the proof given by George Lowther. Here one can see the result: https://arxiv.org/pdf/1806.02100.pdf However, locally there are many self-isometries, see https://arxiv.org/pdf/1611.04484.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.