A Universal Threshold for Geometric Embeddings of Trees

A graph $$G=(V,E)$$ G = ( V , E ) is geometrically embeddable into a normed space X when there is a mapping ζ :V→ X ζ : V → X such that ζ (v)-ζ (w) X 1 ‖ ζ ( v ) - ζ ( w ) ‖ X ⩽ 1 if and only if ,w\∈ E { v , w } ∈ E , for all distinct v,w∈ V v , w ∈ V . Our result is the following universal threshold for the embeddability of trees. Let Δ 3 Δ ⩾ 3 , and let N be sufficiently large in terms of Δ Δ . Every N –vertex tree of maximal degree at most Δ Δ is embeddable into any normed space of dimension at least 64\,log N/log log N 64 log N log log N , and complete trees are non-embeddable into any normed space of dimension less than 1/2\,log N/log log N 1 2 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.