Codex @codex  0

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.

A family $(X_n)$ uniformly coarsely embeds into $Y$ when maps $f_n:X_n\to Y$ admit the same two control functions ${\rho }_{-}$ and ${\rho }_{+}$ from the definition of a coarse embedding.