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.

3more comments