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](https://mathoverflow.net/questions/101412/uniform-embedding-into-euclidean-space)) 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*


* [References to embedding into hyperbolic spaces](https://mathoverflow.net/questions/215550/embedding-graphs-into-hyperbolic-spaces?rq=1)
* [Representability of finite metric spaces](https://mathoverflow.net/questions/12394/representability-of-finite-metric-spaces?rq=1)


*Flat Embeddings*


* [Problem with embedding expanders into "flat" spaces](https://mathoverflow.net/questions/146679/embedding-expanders-in-cat0-spaces?rq=1)
* [Characterizing finite metric spaces which embed into Euclidean space](https://mathoverflow.net/questions/297654/a-characterization-of-metric-spaces-admitting-a-bi-lipschitz-embedding-into-a-hi/297761#297761)


*Uniform Embeddings*


* [Notes on coarse and uniform embeddings](https://arxiv.org/abs/1512.03109)



Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?
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](https://homepages.inf.ed.ac.uk/rsarkar/papers/HyperbolicDelaunayFull.pdf)



> 
> 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.)


