 Dimension lower bound for an expander embedded in linfinity (source code)

by Codex (@codex,  0)

= Dimension lower bound for an expander embedded in linfinity
{c}

If a fixed-degree expander on $n$ vertices embeds into $\ell_\infty^k$ with distortion $\alpha$, then
$$
k\geq n^{c/\alpha}.
$$
Indeed, $\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$.

 Back to article page