9
$\begingroup$

Question

For which pairs $M,N$ of compact metric spaces does there exist a metric space $K$ along with isometric embeddings $i:M \to K$ and $j:N \to K$ so that the Hausdorff distance between $i(M)$ and $j(N)$ in $K$ equals the Gromov-Hausdorff distance between $M$ and $N$ exactly?

We always have $d_\text{GH}(M,N) \leq d_\text{H}(i(M),j(N))$ by definition, so it suffices to decide if there exist any constraints intrinsic to $M$ and $N$ which force the reverse inequality to also hold for some judicious choice of $i,j,K$.

Update

Bill Johnson's nice answer appears to settle the question for compact $M$ and $N$ affirmatively: the Gromov-Hausdorff distance can always be realized by an ultraproduct construction. In light of that answer -- and also in light of the fact that I did not intend to assume compactness in the original question but stupidly wrote it down anyway -- here is a modified question:

Can the GH-distance be similarly achieved if we only assume that $M$ and $N$ are bounded, rather than compact?

In general, I am interested in the weakest hypotheses on $M$ and $N$ which are known to guarantee embeddings into a common target space $K$ so that the Gromov-Hausdorff distance between $M$ and $N$ equals the Hausdorff distance of their isometric images in $K$. It is not clear to me that a modification of Bill's argument works when we drop compactness.

Background

Given a compact metric space $M$ and two subspaces $A, B \subset M$, their Hausdorff distance -- denoted $d_\text{H}(A,B)$ -- is defined to be the smallest $\epsilon > 0$ so that $B$ is contained in $A$ thickened by $\epsilon$ and vice-versa.

The Gromov-Hausdorff distance $d_\text{GH}(M,N)$ between two compact metric spaces $M$ and $N$ is defined to be the infimum over triples $(i,j,K)$ of $d_\text{H}(i(M),j(N))$ where $K$ is a metric space and $i,j$ are isometric embeddings of $M, N$ into $K$. The question asks when this infimum can be explicitly realized.

$\endgroup$
  • $\begingroup$ Do you, or anybody here, know when did the G-H distance appear in a publication for the first time? $\endgroup$ – Włodzimierz Holsztyński Jun 29 '13 at 6:49
  • 1
    $\begingroup$ @Wlodzimierz Holsztynski: GH distance first explicitly appeared in Gromov's green book "Structures métriques pour les variétés riemanniennes". The term "Gromov-Hausdorff distance" was coined (I think) by Karsten Grove. An idea of GH distance goes back to Gromov's paper on groups of polynomial growth. $\endgroup$ – Igor Belegradek Jun 29 '13 at 12:25
  • $\begingroup$ Thank you, @Igor. Thus it was 1981 (the date od publishing the original French edition). $\endgroup$ – Włodzimierz Holsztyński Jun 29 '13 at 20:03
  • $\begingroup$ [Background]----> Do you suppose that the embeddings are such that $i(M)\cap j(N)=\emptyset$ ? $\endgroup$ – Duchamp Gérard H. E. Jan 1 '17 at 10:12
8
$\begingroup$

Unless I am missing something, the distance is achieved for compact metric spaces. Take isometries $i_n :M \to K_n$ and $j_n : N \to K_n$ that give you the Gromov-Hausdorff distance up to $1/n$. Let $K$ be an ultraproduct of the $K_n$ and $i$, $j$ the isometries from $M$, $N$ into $K$ induced by $i_n$, $j_n$. This achieves the distance, I think, when $M$ and $N$ are compact. To see that, given $x$ in $M$ take $y_n$ in $N$ s.t. the distance of $i_n(x) $ to $j_n(y_n)$ is less than the Hausdorff distance from $i_n(M)$ to $j_n(N)$. Let $y$ be the ultralimit of $y_n$ in $N$ (this is where compactness is used). Then the distance from $i(x)$ to $j(y)$ is at most the Gromov-Hausdorff distance from $M$ to $N$.

This is a pretty obvious argument, so I guess it is either written somewhere or is complete nonsense.

$\endgroup$
  • $\begingroup$ Aargh, I have no idea why I wrote compact everywhere. Thank you for this answer though, and please let me also know if there is a similar result if, say, M and N have finite measures of noncompactness. $\endgroup$ – Vidit Nanda Jun 29 '13 at 0:56
  • $\begingroup$ Please state precisely what you want. Maybe I'll think about; maybe not. $\endgroup$ – Bill Johnson Jun 29 '13 at 1:32
0
$\begingroup$

Bounded is not sufficient to ensure that the Gromov-Hausdorff distance is actually achieved. Here is a counterexample:

Let $M$ be a metric space whose underlying set is $\mathbb{N}\times\{0,1\}$ with the following metric: $d((a,i),(b,j))=1$ if $a\neq b$ and $d((a,0),(a,1))=2^{-a}$. Let $N$ be $M$ with a single new point $x$ such that $d(x,y)=1$ for all $y\neq x$. $d_{GH}(M,N)=0$ but this cannot be realized in any common embedding because $M$ and $N$ are not isomorphic.

For bounded metric spaces we can use the formalism of continuous logic to state a few situations in which we can ensure that the distance is actually achieved (although these conditions are probably not very useful).

The first one is for any bounded metric spaces $M$ and $N$ there are elementary extensions $M^\prime \succeq M$ and $N^\prime \succeq N$ and a common embedding $i:M^\prime \rightarrow K $ and $j:N^\prime \rightarrow K$ such that $d_H(i(M^\prime),j(M^\prime))=d_{GH}(M,N)$. You can achieve this with exactly the same argument as in Bill's answer, specifically an ultrapower construction, the only difference is that for non-compact spaces the ultrapower will grow.

The second one is that if $M$ and $N$ are "resplendent" in the model theoretic sense then there will always exist $i:M\rightarrow K$ and $j:N\rightarrow K$ such that $d_H(i(M),j(N))=d_{GH}(i(M),j(N))$. Nobody has bothered to write up the details of how resplendence works in continuous logic but I'm fairly confident that the most common conditions ensuring it will work the same as they do in discrete logic, in particular if you know that $M$ and $N$ have the same density character and are either saturated or special then the Gromov-Hausdorff distance between them will be achieved.

In general though I imagine that for an arbitrary pair of bounded metric spaces this problem is very hard.

$\endgroup$

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.