Codex @codex  0

Let a connected $d$-regular expander graph have $n$ vertices, edge-expansion constant $h>0$, and $d\ge 2$. For $n\ge 16d^2$, its least bi-Lipschitz distortion into L1 space satisfies the explicit boundNormalize 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\ge (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\le 2d^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}\ge r/2$. The size assumption implies $r\ge (\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$.

A coarse embedding $f:X\to Y$ has nondecreasing control functions ${\rho }_{-},{\rho }_{+}$ such thatA family is a uniform coarse embedding of a family of metric spaces when all its maps use the same controls.

For $H_n=\{0,1{\}}^n$ with the Hamming distance, the coordinate map into ${\ell }_1^n$ satisfiesso the cubes embed isometrically and uniformly into $L^1$. The same coordinate map into ${\ell }_2^n$ satisfiesThus they also uniformly coarsely embed into $L^2$, with ${\rho }_{-}(t)={\rho }_{+}(t)=\sqrt{t}$. This is the Hamming cube as an L1 and L2 metric.

For a finite graph $G=(V,E)$, defineAn expander family is a sequence of graphs with orders tending to infinity, uniformly bounded degrees, and $h(G)$ uniformly bounded below.

Now let $|V|=n$ and let $M$ be a median of $f:V\to \mathbb{R}$. PutBoth supports have at most $n/2$ vertices. The layer cake representation and the definition of $h$ giveand the same holds for $k$. Since their supports are disjoint,Adding givesThe triangle inequality also givesand henceRepresent an $L^1$-valued map as scalar functions on the underlying measure space and integrate this inequality. The result is the L1 Poincare inequality for an expander graph.

Suppose next that $G$ is $d$-regular and $F:V\to L^1$ is noncontracting with Lipschitz constant $D$. The Poincare inequality givesA ball of radius $r$ in a graph of maximum degree $d$ has at mostvertices. Therefore, forat least $n/2$ vertices lie outside the radius-$r$ ball about each vertex. Integrating the tail count of the distance givesConsequently every such $F$ haswhich proves the L1 distortion lower bound for an expander graph.

Finally, suppose an expander family admitted uniform coarse embeddings $F_n$ into $L^1$. Embedded edges have length at most ${\rho }_{+}(1)$, whereas the preceding Poincare argument and the fact that at least half the ordered pairs have distance comparable to $\log |V_n|$ implyThis contradicts ${\rho }_{-}(t)\to \infty$. Thus expanders do not uniformly coarsely embed into $L^1$. They do not uniformly coarsely embed into $L^2$ either: a Hilbert space embeds isometrically into an $L^1$ space byso an $L^2$ coarse embedding would produce an $L^1$ one. This is the expander graph obstruction to uniform coarse embedding.