Say that an infinite (connected) graph (with vertices of bounded degree) satisfies a $\ell\_1$-pseudo-Poincaré inequality if there is a constant $C>0$ so that for any $n \in \mathbb{N}$ for any function $f \in \ell\_1(V)$ on the vertices of the graph
$$
\| f - f\_n \|\_{\ell\_1(V)} \leq C \cdot n \cdot \|\nabla f\|\_{\ell\_1(E)}
$$
where


* $f\_n$ is the function defined by: $f\_n(x)$ is the average of the values of $f$ over a ball of radius $n$ centered at $x$, or $f\_n(x) = \displaystyle \frac{1}{|B\_n(x)|} \sum\_{y \in B\_n(x)} f(y)$ where $B\_n(x)$ denotes the ball of radius $n$ around $x$.
* $\nabla f$ is the function on the edges which associate to the edge $(x,y) \in E$ between the vertices $x$ and $y$ the value $f(x) - f(y)$. [It's not important whether on consider edges oriented or not or to be present once with each orientation; at worst, it changes the constant by a factor of 2.]
* $\|g\|\_{\ell\_1}$ are the $\ell\_1$-norms : for functiond defined on the vertices its $\|g\|\_{\ell\_1(V)} = \displaystyle \sum\_{x \in V} |g(x)|$ and for function defined on the edges its $\|g\|\_{\ell\_1(E)} = \displaystyle \sum\_{(x,y) \in E} |g(x,y)|$


I'm pretty sure there are graphs which do not satisfy this inequality, but I could not find any reference. So


**Question:** what are examples of graph which do not satisfy this inequality?


It's known that Cayley graphs satisfy this pseudo-Poincaré inequality. I would be particularly interested in a counterexample which is a subgraph of a Cayley graph (since I my guess would be that this inequality does not pass to subgraphs). A counterexample which is a tree would do the trick.


[Addendum 1]


This $\ell\_1$-pseudo-Poincar\'e inequality is used in groups to show an isoperimetric inequality: 
Let $\phi(\lambda) = \inf \{ n \mid |B\_n| \geq \lambda\}$. Then
$
\frac{ |A|}{\phi(2|A|)} \leq 2C |\partial A|
$


See Coulhon & Saloff-Coste Isopérimétrie pour les groupes et les variétés, Revista Matemática Iberoamericana **9**(2):293--314, 1993. I believe there is a survey from Pittet & Saloff-Coste which contain these proofs and is written in English.


When balls are not isomorphic, I believe one must replace $|B\_n|$ by $b\_n = \displaystyle \inf\_{x \in V} |B\_n(x)|$.


[Addendum 2]


This is how the inequality is proved in case of Cayley graphs (also from Coulhon & Saloff-Coste). 


**Statement:**
Let $G$ be a group and consider the Cayley graph for the generating set $S$.
For any $f \in \ell^1$ (in particular of finite support), $\|f-f\_{n}\|\_1 \leq n \|\nabla f\|\_1$


**Proof:**
First write $f\*\delta\_y$ for the function $(f\*\delta\_y)(x) = f(xy)$ (this is the convolution with a Dirac funtion).


Note that $\|f - f \* \delta\_y\|\_1 \leq \| \nabla f\|\_1$ if $y$ is in $S$. If $y \in B\_n$, then apply the triangle inequality: write $y = s\_1 \ldots s\_n$ with $s\_i \in S$ and
$$
\begin{array}{rl}
\|f - f \* \delta\_y\|\_1
&\displaystyle \leq \| \sum\_{i = 1}^n f \* \delta\_{s\_1 \ldots s\_{i-1}} - f \* \delta\_{s\_1 \ldots s\_i} \|\_1 \\
&\displaystyle \overset{\text{T.I.}}\leq \sum\_{i = 1}^n \|f(\cdot s\_1 \ldots s\_{i-1}) - f(\cdot s\_1 \ldots s\_i) \|\_1 \\
&\displaystyle \leq n \|\nabla f\|\_1 
\end{array}
$$
and then
$$
\begin{array}{rll}
\|f - f\_n\|\_1 
&= \displaystyle \| f - \tfrac{1}{|B\_n|} \sum\_{y \in B\_n }f\* \delta\_y \|\_1 
&= \displaystyle \| \tfrac{1}{|B\_n|} \sum\_{y \in B\_n } f - f\* \delta\_y \|\_1 \\
& \displaystyle \overset{\text{T.I.}}\leq \tfrac{1}{|B\_n|} \sum\_{y \in B\_n } \|f - f\* \delta\_y \|\_1 
& \leq n \|\nabla f\|\_1.
\end{array}
$$
This concludes the proof.



Graph which do not satisfy a pseudo-Poincaré inequality
A counterexample is the subgraph of the $\mathbb{Z}^2$ Cayley graph found by taking squares $S\_i$ of side $i$ and arranging them along a (near)diagonal in a chain so that each $S\_i$ is adjacent to $S\_{i+1}$ along a single edge, and no other edges connect any $S\_i$ to any other.


Suppose the given inequality held. For a given $n$, choose $i > 10n$ and let $f$ be the characteristic function of $S\_i$. Then the right hand side of the inequality is $\sim C n \cdot 2$. On the other hand, for each of the $\sim n^2$ points within distance $n/2$ of the edge between $S\_i$ and $S\_{i+1}$ we have that $f\_n$ is bounded away from $0$ and $1$, and so the left hand side of the inequality is $\gtrsim n^2$.


