= L1 Poincare inequality for an expander graph
{c}
{title2=$\sum a_{xy}\|f(x)-f(y)\|_1\geq\frac h{|V|}\sum_{x,y}\|f(x)-f(y)\|_1$}
If $G$ has adjacency matrix $A=(a_{xy})$ and expansion $h$, then every $L^1$-valued map on its $n$ vertices satisfies
$$
\sum_{x,y}a_{xy}\|f(x)-f(y)\|_1
\geq\frac hn\sum_{x,y}\|f(x)-f(y)\|_1.
$$
For 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.
Back to article page
