# Graph which do not satisfy a pseudo-Poincaré inequality

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.

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

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.

• Do you want to take the $\ell^1$ norm on the whole graph or just on the ball of radius $n$ over which you take the average? In any case, I am sure there is a counterexample, but one needs to construct one. Please, clarify your answer and then I will try to construct a countrexample. – Piotr Hajlasz Jan 24 at 0:28
• @Piotr oh thanks, yes for all $n$. Also the $\ell_1$-norm is on the whole graph (which makes counterexamples easier to find). I'm also sure there are counterexamples. I'm guessing some trees would do the trick. – ARG Jan 24 at 6:10
• I do not understand. Even the line (standard Cayley graph of $\mathbf Z$) is a counterexample : consider $f$ the indicator function of $\{0, \dots,N\}$ for very big $N$. Then $\nabla f$ has $\ell_1$ norm $2$, whereas $f-f_n$ has norm of order $n$ (if $n<N$). – Mikael de la Salle Jan 24 at 8:42
• @MikaeldelaSalle, my bad! I forgot a very important factor of $n$ in the inequality... – ARG Jan 24 at 12:26
• @PiotrHajlasz I kind of disagree on that point. I find it much more natural to define the gradient on the edges. But I'm happy with an answer which uses the other definition of the gradient. – ARG Jan 24 at 16:06

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

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

• @PiotrHajlasz Many thanks for the details in the $\ell^p$-$\ell^q$-case. As I mentioned, the $\ell^1$-inequality is known to hold in all Cayley graphs (not just those of polynomial growth). I added the proof in case you are curious about it. – ARG Jan 24 at 16:08
• @ARG Thank you for details. I was not aware of this result. I will read your proof and erase my stupid comments about counterexamples. – Piotr Hajlasz Jan 24 at 16:51
• @PiotrHajlasz I did not read anything stupid... The reference for the english survey of Pittet and Saloff-Coste is "A survey on the relationships between volume growth, isoperimetry, and the behavior of simple random walk on Cayley graphs, with examples". It is freely available if you google it. The result is section 4 of this survey. – ARG Jan 24 at 16:58