A Universal Threshold for Geometric Embeddings of Trees

Abstract A graph $$G=(V,E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is geometrically embeddable into a normed space X when there is a mapping $$\zeta :V\rightarrow X$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ζ</mml:mi> <mml:mo>:</mml:mo> <mml:mi>V</mml:mi> <mml:mo>→</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> such that $$\Vert \zeta (v)-\zeta (w)\Vert _X\leqslant 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mo>‖</mml:mo> <mml:mi>ζ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>-</mml:mo> <mml:mi>ζ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>w</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>‖</mml:mo> </mml:mrow> <mml:mi>X</mml:mi> </mml:msub> <mml:mo>⩽</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> if and only if $$\{v,w\}\in E$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo>}</mml:mo> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> </mml:mrow> </mml:math> , for all distinct $$v,w\in V$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> </mml:mrow> </mml:math> . Our result is the following universal threshold for the embeddability of trees. Let $$\Delta \geqslant 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>⩾</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , and let N be sufficiently large in terms of $$\Delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> . Every N –vertex tree of maximal degree at most $$\Delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> is embeddable into any normed space of dimension at least $$64\,\frac{\log N}{\log \log N}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>64</mml:mn> <mml:mspace/> <mml:mfrac> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:math> , and complete trees are non-embeddable into any normed space of dimension less than $$\frac{1}{2}\,\frac{\log N}{\log \log N}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mspace/> <mml:mfrac> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:math> . 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.