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*

- Problem with embedding expanders into "flat" spaces
- Characterizing finite metric spaces which embed into Euclidean space

*Uniform Embeddings*

13more comments