L1 Poincare inequality for an expander graph ($\sum a_{xy}\Vert f(x)-f(y){\Vert }_1\ge \frac{h}{|V|}{\sum }_{x,y}\Vert f(x)-f(y){\Vert }_1$)

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 differentiable, increasing, and satisfies $\phi (0)=0$, 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.

If a $d$-regular graph on $n$ vertices has expansion $h$, its $L^1$ distortion obeysThe Poincare inequality controls average image distance by edge lengths, while bounded-degree ball growth makes the average graph distance comparable to $\log n/\log d$.