A graph \(G=(V,E)\) is geometrically embeddable into a normed space X when there is a mapping \(\zeta :V\rightarrow X\) such that \(\Vert \zeta (v)-\zeta (w)\Vert _X\leqslant 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 \(\Delta \geqslant 3\) , and let N be sufficiently large in terms of \(\Delta \) . Every N–vertex tree of maximal degree at most \(\Delta \) 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.
