= L1 distortion lower bound for an expander graph
{c}
Let a connected $d$-regular <expander graph> have $n$ vertices, edge-expansion constant $h>0$, and $d\geq2$. For $n\geq16d^2$, its least <bi-Lipschitz distortion> into <L1 space> satisfies the explicit bound
$$
c_1(G)\geq\frac{h}{4d}\frac{\log n}{\log d}.
$$
Normalize an embedding so that each image distance is at least the graph distance and at most $D$ times it. Every image <edge> has length at most $D$. The <L1 Poincare inequality for an expander graph> then gives $D\geq(h/d)\overline d$, where $\overline d$ is the mean ordered-pair graph distance.
A ball of radius $r$ has at most $1+d+\cdots+d^r\leq2d^r$ vertices. Take $r=\lfloor\log(n/4)/\log d\rfloor$. Its size is at most $n/2$, so at least half the vertices are farther than $r$ from each fixed vertex. Hence $\overline d\geq r/2$. The size assumption implies $r\geq(\log n)/(2\log d)$, proving the bound. For a fixed-degree family with expansion bounded below, distortion therefore grows at least proportionally to $\log n$.
Back to article page
