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)$.

A Frechet embedding uses distance functions as coordinates, typicallyfor selected subsets $A_i$. Every coordinate is one-Lipschitz, and suitable subsets provide lower bounds on pairwise image distances.

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$.