Expander graph

For a finite graph $G=(V,E)$, its edge-expansion constant isAn expander family has uniformly bounded degrees, orders tending to infinity, and expansion constants bounded below by a positive constant.

For a port-labeled $D$-regular graph $G$ and a $d$-regular graph $H$ on its $D$ port labels, replace every vertex by a copy of $H$. An edge makes a step in $H$, crosses the corresponding edge of $G$, then makes another step in $H$. The result has $|G|D$ vertices and degree $d^2$. Its normalized operator is $BRB$, where $B=I\otimes P_H$ and $R$ is the involutive edge rotation of $G$. Decomposing a mean-zero vector into cloud-constant and cloud-orthogonal parts proves the bound $\rho (G\mathrm{zigzag}H)\le \rho (G)+2\rho (H)+\rho (H{)}^2$.

Choose $D=d^2$ and a fixed $d$-regular graph $H$ on $D^2$ vertices with absolute nonconstant eigenvalues at most $1/10$. Start with the loop-inclusive complete graph $G_0$ on $D$ vertices and iterate $G_{t+1}=G_t^2\mathrm{zigzag}H$. The degree stays $D$, vertex counts are $D^{2t+1}$, and ${\rho }_{t+1}\le {\rho }_t^2+21/100$. Since ${\rho }_0=0$, all ${\rho }_t\le 1/2$. The spectral cut bound gives multiplicity-counted edge expansion at least $D/4$. Removing loops and merging parallel edges loses at most a factor $D$, producing simple expander graphs with maximum degree $D$ and edge expansion at least $1/4$.

If $G$ has adjacency matrix $A=(a_{xy})$ and expansion $h$, then every $L^1$-valued map on its $n$ vertices satisfiesFor scalar functions this follows from the layer-cake formula applied above and below a median; integration over the $L^1$ coordinate proves the vector-valued form.

For a nonnegative measurable function $g$,On a graph, applying this identity to $|g(x)-g(y)|$ expresses its total variation as the integral of the edge boundaries of the superlevel sets.

More generally, if $\phi :[0,\infty )\to [0,\infty )$ is an absolutely continuous function on every compact interval, is increasing, and satisfies $\phi (0)=0$, with its nonnegative derivative defined almost everywhere, then Tonelli theorem and the fundamental theorem of calculus give

Let $F,G\ge 0$, $1<p<\infty$, and $G\in L^p$. Assume the displayed tail inequality and finite positive-threshold superlevel measures. First split $G$ at $a/2$ to obtain $a\mu \{F>2a\}\le {\int }_{\{G>a\}}G$. Layer cake representation and Tonelli theorem imply $F\in L^p$. Integrating the original inequality against $p{a}^{p-2}$ then gives $\Vert F{\Vert }_p^p\le q\int G{F}^{p-1}\le q\Vert G{\Vert }_p\Vert F{\Vert }_p^{p-1}$, with $q=p/(p-1)$. This is the analytic estimate behind the Doob Lp maximal inequality.

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

An expander family does not uniformly coarsely embed into $L^1$ or $L^2$. Uniform upper control bounds every embedded edge, whereas the expander Poincare inequality bounds the average image distance. A fixed proportion of vertex pairs have graph distance tending to infinity, contradicting the lower control. The $L^2$ case also follows from the isometric Gaussian embedding of a Hilbert space into $L^1$.