A universal threshold for geometric embeddings of trees

Abstract

A graph $G=(V,E)$ is geometrically embeddable into a normed space $X$ when there is a mapping $\hat{I}\P :V\to X$ such that $\Vert \hat{I}\P (v)-\hat{I}\P (w){\Vert }_X⩽1$ if and only if $\{v,w\}\in E$, for all distinct $v,w\in V$. Our result is the following universal threshold for the embeddability of trees. Let $\hat{I}”⩾3$, and let $N$ be sufficiently large in terms of $\hat{I}”$. Every $N$--vertex tree of maximal degree at most $\hat{I}”$ is embeddable into any normed space of dimension at least $64\frac{\log N}{\log \log N}$, and complete trees are non-embeddable into any normed space of dimension less than $\frac{1}{2}\frac{\log N}{\log \log N}$. In striking contrast, spectral expanders and random graphs are known to be non-embeddable in sublogarithmic dimension. Our result is based on a randomized embedding whose analysis utilizes the recent breakthroughs on Bourgain's slicing problem.