16
$\begingroup$

EDIT: now crossposted at mathoverflow (https://mathoverflow.net/questions/212364/on-the-global-structure-of-the-gromov-hausdorff-metric-space)

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.

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 isometries of $\mathcal{GH}$?

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


Please feel free to add tags; I couldn't think what to label this question.

$\endgroup$
  • $\begingroup$ what's $Z{}{}$ ? $\endgroup$ – mercio Jul 24 '15 at 21:23
  • $\begingroup$ Any other metric space at all. The sup/inf is taken over all embeddings into all metric spaces. $\endgroup$ – Noah Schweber Jul 24 '15 at 21:26
  • 2
    $\begingroup$ As a small first step, any isometry must fix the space, $P$, consisting of a single point. This is because it is the only space satisfying $d_H(A,B)\le\max(d_H(A,P),d_H(B,P))$. Then, because the diameter of a space $A$ equals $2d_H(A,P)$, the isometry preserves the diameter of all spaces. $\endgroup$ – George Lowther Jul 27 '15 at 2:40
  • $\begingroup$ This has been answered at mathoverflow by George Lowther: mathoverflow.net/questions/212364/…. @GeorgeLowther if you want to post your answer here too for convenience, I'll accept it. $\endgroup$ – Noah Schweber Aug 2 '15 at 23:48
2
$\begingroup$

This question has been asked and answered on MathOverflow. I have replicated the accepted answer by George Lowther below.

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$
1
$\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$
  • $\begingroup$ This is a comment, not an answer. $\endgroup$ – Taroccoesbrocco Jul 26 '18 at 7:36
  • $\begingroup$ Sorry, I can not add comments because I do not have 50 reputations $\endgroup$ – Alexey Tuzhilin Jul 26 '18 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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