Low-dimensional Frechet embedding into linfinity ($X\hookrightarrow {\ell }_{\infty }^k$)

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