17
$\begingroup$

There is a folklore in the empirical computer-science literature that, given a tree $(X,d)$, one can find a bi-Lipschitz embedding into a hyperbolic space $\mathbb{H}^n$ and that $n$ is "much smaller" than the smallest dimension of a Euclidean space in which $(X,d)$ can be bi-Lipschitz embedded with similar distortion.

Question A: Is there any theoretical grounding to this claim? Namely, can one prove that $(X,d)$ (where $\# X = n\in\mathbb{N}_+$) admits a bi-Lipschitz embedding into some $\mathbb{H}^n$ with:

  • distortion strictly less that $O(\log(n))$
  • $n<O(\log^2n)$?

! Edit - (Following Discussion of YCor, WillSawin, and TomTheQuant): What can be said if $s=1$ in Equation (1)?

Question B (Converse): For every $n\in \mathbb{N}_+$ and every $D>0$ does there exist a finite metric space $(X,d)$, which don't admit a bi-Lipschitz (resp. possibly uniform embedding) into $\mathbb{H}^n$ with distortion at-most $D$?

Relevant Definition (For completeness)

A bi-Lipschitz embedding $f:X\rightarrow \mathbb{H}^n$ of a metric space $(X,d)$ into $\mathbb{H}^n$ with distortion $D>0$ is a Lipschitz homeomorphism $f:X\rightarrow \mathbb{H}^n$ Lipschitz inverse $f^{-1}$ such that there is some $s>0$ satisfying $$ sd(x_1,x_2) \leq d_{\mathbb{H}^n}(f(x_1),f(x_2)) \leq sDd(x_1,x_2) \qquad (1) $$ for every $x_1,x_2\in X$. Here, $d_{\mathbb{H}^n}$ is the usual geodesic distance on the $n$-dimensional hyperbolic space.

Some Relevant posts:

Hyperbolic embeddings

Flat Embeddings

Uniform Embeddings

$\endgroup$
18
  • 4
    $\begingroup$ Are you implicitly assuming that $X$ is finite? Infinite trees (of bounded valency) can be bilipschitz-embedded into the hyperbolic space $\mathbb{H}^2$, but not into any Euclidean (or even Hilbert) space. $\endgroup$
    – YCor
    Feb 8, 2022 at 12:33
  • 4
    $\begingroup$ That infinite bushy trees (bushy= of valency $\ge 3$ at every vertex) can't be embedded bilipschitz into Hilbert spaces is a result of Bourgain in the 80s (that they can't be embedded bilipschitz or even uniformly into Euclidean spaces just follows from growth conditions). $\endgroup$
    – YCor
    Feb 8, 2022 at 13:56
  • 2
    $\begingroup$ For embedding a bilipschitz tree of constant valency $\ge 3$ into the hyperbolic plane, there are plenty of ways. I don't know what is the first reference. One can produce this with actions of free groups; in this way the earliest reference is possibly Schottky. One can also inscribe such trees in regular tilings. $\endgroup$
    – YCor
    Feb 8, 2022 at 13:59
  • 1
    $\begingroup$ A finite metric space can trivially be embedded bilipschitz into any infinite space (take any injective map). The issue is only to do it with good constants. $\endgroup$
    – YCor
    Feb 8, 2022 at 14:15
  • 2
    $\begingroup$ And actually that we can rescale (this time, to large scale) makes it quite immediate that every finite (weighted) tree can be embedded with distortion $\le 1+\varepsilon$ into the hyperbolic plane (since it embeds isometrically into the asymptotic cone of $H^2$ which is a real tree). $\endgroup$
    – YCor
    Feb 8, 2022 at 16:30

2 Answers 2

7
$\begingroup$

I am not sure if the following paper answers your question. The abstract suggests so, but it is written in a computer science style that is less transparent to me in terms of stating a precise theorem. Also: (a) I am not an expert, (b) I am confused by the way that $n$ seems to play two different roles in your question, and (c) I doubt if it is the earliest answer to your question, if indeed it does answer it.

Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane by Rik Sarkar

Abstract. This paper considers the problem of embedding trees into the hyperbolic plane. We show that any tree can be realized as the Delaunay graph of its embedded vertices. Particularly, a weighted tree can be embedded such that the weight on each edge is realized as the hyperbolic distance between its embedded vertices. Thus the embedding preserves the metric information of the tree along with its topology. Further, the distance distortion between non adjacent vertices can be made arbitrarily small – less than a $(1+\epsilon)$ factor for any given $\epsilon$. Existing results on low distortion of embedding discrete metrics into trees carry over to hyperbolic metric through this result. The Delaunay character implies useful properties such as guaranteed greedy routing and realization as minimum spanning trees.

(bolding is mine.)

$\endgroup$
1
  • 2
    $\begingroup$ @Carl_Petterson Regardless of the quality of the paper, I think the key claim is correct and answers your first question - we can embed any finite tree into the hyperbolic plane with distortion $D = 1+\epsilon$ for any $\epsilon>0$, by taking $s$ sufficiently large (proportional to $(1+\epsilon)/\epsilon)$. (I was in fact planning to type a (trivial) proof of this before seeing this answer.) $\endgroup$
    – Will Sawin
    Feb 8, 2022 at 18:56
3
$\begingroup$

Here is a trivial example for question B (in the $s=1$ case):

The discrete metric space on $N$ points with distance 1 between every two distinct points has the minimal distortion of an embedding into $\mathbb H^n$ going to $\infty$ as $N$ goes to $\infty$ with respect to $n$.

Indeed, for an embedding of distortion $D$, any two points in the embedding must have distance at least $1$, so the balls of radius $1/2$ around these points must be disjoint. But every two points have distance at most $D$, so the balls of radius $1/2$ around these points must be contained in the ball of radius $D+1/2$ around one point.

Thus, for an embedding to exist, the volume of the ball of radius $D+1/2$ must be at least $N$ times the volume of the ball of radius $1/2$.

Thus $D$ must go to $\infty$ if $N$ goes to $\infty$ with fixed $n$.

$\endgroup$
2
  • $\begingroup$ Do you think this type of argument can be generalized to @A_K's setting, or is it exclusive to hyperbolic space? $\endgroup$ Feb 9, 2022 at 12:45
  • 1
    $\begingroup$ @Carl_Petterson We need a lower bound for the volume of small balls and an upper bound for the volume of large balls. This should exist in a Riemannian manifold with sectional curvature bounded above and below under mild conditions (a lower bound on the injectivity radius). I don't think this strategy can be generalized to spaces of Markov type. $\endgroup$
    – Will Sawin
    Feb 9, 2022 at 13:20

Your Answer

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

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