Bourgain embedding theorem

Every metric space with $n$ points admits an embedding into a Hilbert space with distortion $O(\log n)$. The usual random-subset construction gives an embedding into Euclidean dimension $O((\log n{)}^2)$.

Fix a point $x_0$ in a metric space $X$. The Fréchet embedding sends $x$ to the bounded function $a\mapsto d(x,a)-d(x_0,a)$ in ${\ell }^{\infty }(X)$. The triangle inequality bounds each coordinate by $d(x,x_0)$ and gives $\Vert f_x-f_y{\Vert }_{\infty }\le d(x,y)$. Taking $a=x$ gives equality, so the map is an isometric embedding. For a separable metric space a countable dense set of anchors suffices. Finite collections of distances to selected subsets instead give one-Lipschitz coordinates that need not be an exact Fréchet embedding.

For every integer $q\ge 2$, every $n$-point metric space embeds into ${\ell }_{\infty }^k$ with distortion at most $2q-1$ andThe coordinates are distance-to-subset functions. Randomly sampled subsets at $q$ density scales separate every pair at one scale; a union bound leaves the stated number of coordinates.

If a fixed-degree expander on $n$ vertices embeds into ${\ell }_{\infty }^k$ with distortion $\alpha$, thenIndeed, ${\ell }_{\infty }^k\hookrightarrow {\ell }_p^k$ has distortion $k^{1/p}$, while $c_p(G)\gtrsim (\log n)/p$. Taking $p\asymp \log k$ gives $\log k\gtrsim (\log n)/\alpha$.