Graph which do not satisfy a pseudo-Poincaré inequality

Question

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.

Answer 1

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

Answer 2

Why I do not have a relevant counterexample yet, I decided to write an extended comment on related Poincaré and Sobolev inequalities. The purpose was to place the question in the right context, provide a source that contains many related references and mention a result (inequality (*)) in the positive direction that is strictly related to the inequality in the question.

A lot is known about Poincaré inequalities on Cayley graphs of finitely generated groups of polynomial growth.

Denote by $|B|$ volume (number of points) in a of a ball $B$. Denote also by $f_B$ average of $f$ on $B$. Also $|\nabla f(x)|=\sum_{y\sim x}|f(x)-f(y)|$ where $x\sim y$ mean that $x$ and $y$ are connected by an edge.

Theorem. If $G$ is a finitely generated group of polynomial growth i.e. volume of a ball of radius $n$ in the associated Caley graph is $\approx n^d$ for some positive integer $d$. Then for any ball $B$ of radius $n$ the following Sobolev-Poincare inequality is true: $$ \left(\frac{1}{|B|}\sum_{x\in B}|f(x)-f_B|^q\right)^{1/q}\leq C n \left(\frac{1}{|B|}\sum_{x\in B}|\nabla f(x)|^p\right)^{1/p} $$ where $1\leq p<d$ and $1\leq q\leq dp/(d-p)$. The constant $C$ does not depend on $B$.

In particular taking $p=q=1$ yields $$ \sum_{x\in B}|f(x)-f_B|\leq C n \sum_{x\in B}|\nabla f(x)| \qquad\qquad (*) $$

This is similar to your inequality but the difference is that you take the $\ell^1$ norm on the ball and not on the whole graph. Also the graph cannot be arbitrary. You need some structure in order to prove the Poincaré inequality.

For a proof of the above result and many references see:

P. Hajłasz, P. Koskela, Sobolev met Poincaré. Mem. Amer. Math. Soc. 145 (2000), no. 688.