ANNALES MATHÉMATIQUES BLAISE PASCAL

SÉBASTIEN BLACHÈRE

Harmonic functions on annuli of graphs

Annales mathématiques Blaise Pascal, tome 8, n° 2 (2001), p. 47-59

<http://www.numdam.org/item?id=AMBP_2001__8_2_47_0>

© Annales mathématiques Blaise Pascal, 2001, tous droits réservés.

L'accès aux archives de la revue « Annales mathématiques Blaise Pascal » (http://math.univ-bpclermont.fr/ambp/) implique l'accord avec les conditions générales d'utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d'une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

NUMDAM

Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/
# Harmonic functions on annuli of graphs

Sébastien Blachère

## Abstract

In this paper, we prove the "relative connectedness" of graphs which satisfy a polynomial volume growth and a Poincaré-type inequality on balls. By "relative connectedness", we mean that every two vertices at distance $R$ from a vertex $x$ can be joined by a path within an annulus $A(x, \alpha^{-1}R, \alpha R)$. We apply this result first to control the behavior of harmonic functions outside a ball and then, in the case of Cayley graph of groups having polynomial volume growth, to obtain a Poincaré-type inequality on the annuli.

## 1 Introduction

Let $\Gamma$ be an infinite undirected connected graph and note that we call $\Gamma$ both the graph and its set of vertices when there is no ambiguity. Let two vertices $x$ and $y$ be neighbors (denoted $x \sim y$) when $\Gamma$ has an edge between them. We also suppose the graph to be locally uniformly finite, which means:

$$ \exists K > 0, \forall x \in \Gamma \ \#\{y \in \Gamma : y \sim x\} \le K. $$

Let $d(x, y)$ be the natural distance on $\Gamma$, that is the minimal number of edges between $x$ and $y$. Then we denote $S(x, R) = \{y \in \Gamma : d(x, y) = R\}$ and $B(x, R) = \{y \in \Gamma : d(x, y) < R\}$ the sphere and the ball of radius $R$, centered at $x$.

We say that the spheres of $\Gamma$ (with respect to $d$) are relatively connected if there exist constants $R_0 > 0$ and $\alpha > 1$ such that: for any $R > R_0$ and any vertex $x \in \Gamma$, every two vertices in the sphere $S(x, R)$ can be joined by a path within the annulus $A(x, \alpha^{-1}R, \alpha R) = B(x, \alpha R) \setminus B(x, \alpha^{-1}R)$.

We suppose that $\Gamma$ has polynomial volume growth of exponent $D$:

$$ \exists C, D > 1, \forall x \in \Gamma, R > 0 \ C^{-1}R^D \le \#B(x, R) \le CR^D. \quad (1.1) $$
Our aim is first to prove the relative connectedness of the spheres of $\Gamma$ (Proposition 2.1) when it satisfies (1.1) and a D-Poincaré-type inequality on balls: there is a constant $C(D)$ such that for any function $u$ on $\Gamma$,

$$ \forall x \in \Gamma, R > 0, \quad \sum_{y \in B(x,R)} |u(y) - u_{B(x,R)}|^D \le C(D)R^D \sum_{y \in B(x,2R)} |\nabla u(y)|^D, \qquad (1.2) $$

where $u_B = \frac{1}{\#B} \sum_{y \in B} u(y)$ for any set $B$, and

$$ \nabla u(x) = \sum_{y \sim x} |u(y) - u(x)|. $$

The method is adapted from [5, Prop. 4.5] to our discrete setting. We will give the whole proof for the sake of completeness. Note that, for instance, the above assumptions are satisfied for Cayley graphs of groups with polynomial growth of exponent $D \ge 2$ [7, Th. 4.1].

Then, we extend to annuli (Theorem 3.1) the elliptic Harnack inequality on balls obtained by Delmotte [2] under (1.2) and the doubling of the volume (implied by (1.1)). From this inequality, we deduce a control on the behavior of harmonic functions outside a finite set (Theorem 3.2), by comparison with the behavior of the Green function. Finally, when $\Gamma$ is the Cayley graph of a group having polynomial volume growth, we deduce Poincaré-type inequalities on annuli (Theorem 3.3).

## 2 Relative connectedness of the spheres

**Proposition 2.1** Let $\Gamma$ be an infinite, locally uniformly finite, undirected connected graph which satisfies (1.1) and (1.2). Then, the spheres of $\Gamma$ are relatively connected.

**PROOF:** First, note that the definition (1.2) of the D-Poincaré-type inequality differs from the one in [5], which is, under the same conditions,

$$ \frac{1}{\#B(x, R)} \sum_{y \in B(x, R)} |u(y) - u_{B(x, R)}| \le C(D) \left( \sum_{y \in B(x, 2R)} |\nabla u(y)|^D \right)^{1/D} . \quad (2.3) $$

Indeed, (2.3) is a consequence of (1.2) and Hölder inequality, and will be used below. Actually, (1.2) and (2.3) are equivalent (see [5]).
Let $x \in \Gamma$ and $R \in \mathbb{N}^*$ be large enough. Let $x_1, x_2$ be two vertices on $S(x, R)$ and take $\alpha > 21$. If $d(x_1, x_2) \le \alpha^{-1}R$, then they can be joined within $A(x, \alpha^{-1}R, \alpha R)$. So we only need to consider $d(x_1, x_2) > \alpha^{-1}R$. Let $F_1$ (resp. $F_2$) be a path from $x_1$ (resp. $x_2$) to $S(x, R/2)$ of length $R/2$. We suppose there is no path between $F_1$ and $F_2$ within $A(x, \alpha^{-1}R, \alpha R)$, and will prove that this becomes impossible for large $\alpha$.

Let $u$ be a function on $A(x, \alpha^{-1}R, \alpha R)$ such that $u \equiv 0$ on $F_1$ and $u(y) \ge 1$ for $y \in F_2$. Suppose $u_{B(x,R)} \le 1/2$ and let $y \in F_2$, then $|u_{B(x,R)} - u(y)| \ge 1/2$.

Let $B_i = B(y, 2^{2-i}R)$ and $C$ be a constant whose value may change from one line to another. Then by (1.1), as $B(x, R) \subset B_1$,

$$ 
\begin{aligned}
|u_{B(x,R)} - u(y)| &\le |u_{B(x,R)} - u_{B_1}| + |u_{B_1} - u(y)| \\
&\le |u_{B(x,R)} - u_{B_1}| + \sum_{i=1}^{\infty} |u_{B_{i+1}} - u_{B_i}| \\
&\le 2C \sum_{i=1}^{\infty} \frac{1}{\#B_i} \sum_{z \in B_i} |u(z) - u_{B_i}|.
\end{aligned}
$$

So, using (2.3), we obtain

$$ 
\begin{aligned}
|u_{B(x,R)} - u(y)| &\le C \sum_{i=0}^{\infty} \left( \sum_{z \in B_i} |\nabla u(z)|^D \right)^{1/D} \\
&\le C R^{1/D} \sup_{r<4R} \left( r^{-1} \sum_{z \in B(y,r)} |\nabla u(z)|^D \right)^{1/D} \sum_{i=0}^{\infty} 2^{(2-i)/D}.
\end{aligned}
$$

So, there is a constant $C$ depending on $D$ and the constants from (1.1) and (1.2), such that for each $y \in F_2$, there is a radius $r(y) < 4R$ with

$$ \sum_{z \in B(y,r(y))} |\nabla u(z)|^D \ge Cr(y)/R. $$

By the covering Lemma [5, Th. 14.12], among all the $B(y, r(y))$, there is a sub-collection of balls $B(y_i, r(y_i))$ ($y_i \in F_2$), pointwise disjoint, such that $F_2 \subset \cup_i B(y_i, 5r(y_i))$. As a consequence, by definition of $F_2$, we must have $\sum_i r(y_i) \ge R/20$. So,

$$ \sum_{z \in B(x, 5R)} |\nabla u(z)|^D \ge C \sum_i \sum_{z \in B(y_i, r(y_i))} |\nabla u(z)|^D \ge C' $$
If $u_{B(x,R)} \ge 1/2$, then taking $F_1$ instead of $F_2$ leads to the same result. Finally

$$ \sum_{z \in B(x, 5R)} |\nabla u(z)|^D \ge C'. \quad (2.4) $$

As $C'$ does not depend on $\alpha$, the aim is to choose $u$ such that the left hand side of (2.4) tends to 0 as $\alpha$ goes to infinity.

Let $g(z) = (\ln \alpha)^{-1} d(x, z)^{-1}$ when $z \in A(x, \alpha^{-1}R, \alpha R)$ and 0 elsewhere. We define the function

$$ u(z) = \inf_{\gamma_z} \sum_{y \in \gamma_z} g(y), $$

where the $\gamma_z$'s are the paths from $z$ to $F_1$. Then $u \equiv 0$ on $F_1$ and, assuming that $F_1$ and $F_2$ cannot be joined within $A(x, \alpha^{-1}R, \alpha R)$, any path between them must leave the annulus. If it does so through its exterior boundary, the path should go from $S(x, R)$ to $S(x, \alpha R)$ and come back. Likewise, if the path exits the annulus through its interior boundary, it should go from $S(x, R/2)$ to $S(x, \alpha^{-1}R)$ and come back. Then, for $y \in F_2$, we obtain

$$ u(y) \ge \min \left\{ (\ln \alpha)^{-1/2} \sum_{k=R}^{\alpha R} k^{-1}, (\ln \alpha)^{-1/2} \sum_{k=\alpha^{-1}R}^{R/2} k^{-1} \right\} \ge 1. $$

For any $z \in A(x, \alpha^{-1}R, \alpha R)$ and $z' \sim z$, we easily see that

$$ |u(z) - u(z')| \le \max\{g(z), g(z')\} \le 2g(z). $$

So, $|\nabla u(z)|^D \le K 2^D g(z)^D$, where $K$ is a uniform bound for the number of neighbors.

Then, to prove that (2.4) leads to a contradiction it is sufficient to obtain

$$ \sup_R \sum_{z \in B(x, 5R)} g(z)^D \xrightarrow{\alpha \to \infty} 0. \quad (2.5) $$

Taking the supremum over $R$ gives the uniformity in $R$ of the constant $\alpha$. Using the definition of $g$, we obtain

$$ \begin{aligned} \sum_{z \in A(x, \alpha^{-1}R, \alpha R)} g(z)^D &\le (\ln \alpha)^{-D} \sum_{i=0}^{[2 \log_2 \alpha]} \sum_{z \in A(x, 2^i \alpha^{-1} R, 2^{i+1} \alpha^{-1} R)} d(x, z)^{-D} \\ &\le (\ln \alpha)^{-D} ([2 \log_2 \alpha] + 1) C 2^D. \end{aligned} $$
The last inequality uses $\#A(x, 2^i\alpha^{-1}R, 2^{i+1}\alpha^{-1}R) \le C(2^{i+1}\alpha^{-1}R)^D$. Since $g \equiv 0$ on $B(x, \alpha^{-1}R)$ and $D > 1$, we obtain (2.5) and then the result. $\square$

*Remark:* In the hypothesis of Proposition 2.1, if we replace $D$ by $p > D$ in the Poincaré-type inequality, the result fails. Indeed, take $\Gamma$ the graph made of two copies of the two-dimensional lattice joined by a single edge. This graph, with polynomial volume growth of exponent 2, satisfies the above assumptions, but not a 2-Poincaré-type inequality, whereas the relative connectedness clearly fails. Conversely, the p-Poincaré-type inequality with $1 \le p < D$ is stronger than the D-Poincaré-type inequality.

In the sequel, we will always denote $\alpha$ and $R_0$ the constants related to the relative connectedness of the spheres. Now, we give a control of the length of the path between two vertices of a sphere of $\Gamma$, within the annulus defined in Proposition 2.1.

**Proposition 2.2** *Under the hypothesis of Proposition 2.1, there exists a positive constant $\lambda$ such that, for all $R > R_0$ and all $x_1, x_2$ on the sphere $S(x, R)$ of $\Gamma$, there is a path from $x_1$ to $x_2$, within the annulus $A(x, (2\alpha)^{-1}R, 2\alpha R)$, of length at most $\lambda R$.*

**PROOF:** By Proposition 2.1, we can pick one path between $x_1$ and $x_2$ within $A(x, \alpha^{-1}R, \alpha R)$. Let us take a sequence $(v_i)$ of vertices on this path oriented from $x_1$ to $x_2$, by the following rules:

* $v_1 = x_1$,

* Given $v_i$, $v_{i+1}$ is the last vertex along this path at distance $[\alpha^{-1}R/2]$ (the lowest greater integer) from $v_i$,

* We stop at $i = I$ when $x_2$ belongs to the ball $B(v_I, [\alpha^{-1}R/2])$.

Such a sequence exists and is finite. Note that all the balls $B(v_i, \alpha^{-1}R/4)$ are disjoint by construction. Recall the constant $C$ in (1.1). All these balls are included in $B(x, (\alpha+\alpha^{-1}/2)R)$, whose volume is less than $C(\alpha+\alpha^{-1}/2)^D R^D$. On the other hand

$$ \sum_{1 \le i \le I} \#B(v_i, \alpha^{-1}R/4) \ge IC^{-1}(4\alpha)^{-D}R^D. $$
Hence we must have $I \le C^2(\alpha + \alpha^{-1/2})^D(4\alpha)^D$. Note also that all the $B(v_i, [\alpha^{-1}R/2])$ are included in $A(x, (2\alpha)^{-1}R, 2\alpha R)$. Then, within this annulus, there are paths from $v_i$ to $v_{i+1}$ of length $[\alpha^{-1}R/2]$. So, the annulus $A(x, (2\alpha)^{-1}R, 2\alpha R)$ contains a path between $x$ and $y$ of length less than $\lambda R$ with $\lambda = 4C^2(\alpha + \alpha^{-1/2})^D(4\alpha)^{D-1}$. $\square$

### 3 Behavior of harmonic functions outside a ball

We always suppose $\Gamma$ to be an infinite, locally uniformly finite, undirected connected graph which satisfies (1.1) and (1.2). A function $f$ on $\Gamma$ is called **harmonic** on a set of vertices $E$ if

$$ \text{for all } x \in E, \quad \Delta f(x) = \sum_{y \sim x} (f(x) - f(y)) = 0. $$

Likewise we call a function sub-harmonic (resp. super-harmonic) if $\Delta f(x) \le 0$ (resp. $\Delta f(x) \ge 0$).

Let $u$ be a non-negative function defined on $\Gamma$, harmonic on an annulus $A(z, s, t) = B(z, t) \setminus B(z, s)$. We write $A(s, t)$ for $A(z, s, t)$. Recall the constant $\alpha$ from Proposition 2.1. First we extend to annuli an **elliptic Harnack inequality** on balls.

**Theorem 3.1** Assume that $s > R_0$ ($R_0 > 0$ large enough), and $t/\alpha > 4s\alpha$. Let $u$ be a non-negative function defined on $\Gamma$, harmonic on $A(s, t)$. Then $u$ satisfies an elliptic Harnack inequality on the annulus $A(2s\alpha, t/(2\alpha))$, namely:

$$ \max_{A(2s\alpha, t/(2\alpha))} u \le c(t/s) \min_{A(2s\alpha, t/(2\alpha))} u, $$

where $c(t/s)$ is a constant depending only on $t/s$ and the graph.

**PROOF:** Let $x, y$ be in $A(2s\alpha, t/(2\alpha))$. By Proposition 2.1, there is a path between $x$ and $y$ within $A(2s, t/2)$. We first take a sequence of vertices $v_i$ ($i = 1$ to $I$) along this path, as in the proof of Proposition 2.2, with $[s/3]$ instead of $[\alpha R/2]$ for the distance between two successive vertices. Then, we obtain that $I \le c(t/s)^D$ where $D$ is the constant in (1.1).

With (1.1) and (1.2), Delmotte [2] has proved that an harmonic function on a ball $B(x, 2n)$ satisfies an elliptic Harnack inequality on $B(x, n)$ whose constant is independent of $x$ and $r$:

$$ \max_{B(x,n)} u \le c \min_{B(x,n)} u. $$
We can apply this result for $u$ on all the balls $B(v_i, s/6)$, because their doubles $B(v_i, s/3)$ are all included in $A(s, t)$. Moreover we can write the Harnack inequality on the union of all these balls, putting the constant to the power $I$ depending only on $t/s$. The result follows. $\square$

We have an immediate corollary.

**Corollary 3.1** Let $u$ be a non-negative function defined on $\Gamma$, harmonic outside a ball $B(z, N)$ ($z \in \Gamma$ and $N > 0$). There exists $N_0 \ge N$ such that $u$ satisfies an elliptic Harnack inequality on all the dyadic annuli $A(z, 2^n, 2^{n+1})$ ($2^n > N_0$) with the same constant $C_h$.

Now, we take the hypothesis of the previous corollary, and we study the asymptotic behavior of such a function $u$. We begin by an analysis made by Moser in [6] about its oscillations on the spheres. Since the center $z$ is fixed, we denote $|x| = d(z, x)$. We define:

$$M(r) = \max_{|x|=r} u(x) \quad \text{and} \quad m(r) = \min_{|x|=r} u(x).$$

Suppose $M(r)$ has two relative minima, say $r_1$ and $r_2$ ($r_2 > r_1$). Then, in the annulus $A(r_1, r_2)$, $M(r)$ attains his maximum inside the domain, so does $u$. This contradicts the maximum principle. So we are left with two cases: either $M(r)$ has one relative minimum at $\bar{r}$ and so $M(r)$ is increasing for $r > \bar{r}$. Or $M(r)$ has no relative minimum and so it is decreasing.

Likewise we see that $m(r)$ has at most one relative maximum $\underline{r}$. Therefore either $m(r)$ is decreasing for $r > \underline{r}$, or $m(r)$ is increasing. Finally, for $r$ bigger than some $r_0$, $M(r)$ and $m(r)$ are both monotone, and we have four cases:

* Case 1: $M(r) \nearrow$ and $m(r) \searrow$

* Case 2: $M(r) \searrow$ and $m(r) \nearrow$

* Case 3: $M(r) \nearrow$ and $m(r) \searrow$

* Case 4: $M(r) \searrow$ and $m(r) \nearrow$

We denote $\text{osc}(r) = M(r) - m(r)$, the oscillations of $u$ on the sphere of radius $r$. The following proposition mimics [6, Th 4,5].

**Proposition 3.1** Let $C_h$ be the constant of Corollary 3.1, then:
(i) Case 1 implies that osc(r) tends to infinity at least like a power p of r, and

$$p = \log_2((C_h + 1)/(C_h - 1)).$$

(ii) Cases 2, 3, 4 imply that osc(r) tends to zero. Hence:

$$\lim_{|x|\to\infty} u(x) = u_\infty \text{ exists.}$$

Remark:

* As the four cases cover all possibilities, (i) and (ii) correspond respectively to u unbounded and u bounded.

* For case 2, the proof of Moser gives also that osc(r) tends to zero at most like a power $p' = \log_2((C_h - 1)/(C_h + 1))$ of r.

For cases 2,3,4, we want to bound $|u(x) - u_\infty|$ by an explicit power of $|x|$ which depends only on the constant D.

**Theorem 3.2** Suppose $\Gamma$ has exponent $D > 2$. Let $u$ be a bounded (by say $U$) function on $\Gamma$, harmonic outside a ball $B(z, N)$ ($z \in \Gamma$ and $N > 0$), then:

$$\lim_{|x|\to\infty} u(x) = u_\infty \text{ exists,}$$

and

$$|u(x) - u_\infty| \le cN^{D-2}U|x|^{2-D},$$

where c is a positive constant depending only on $\Gamma$.

**PROOF:** First note that we can restrict ourselves to the non-constant functions. To apply Corollary 3.1, we need to consider only the $x$'s such that $|x| > N_0$ with some $N_0$ large enough. Actually, we only need $N_0 = C'N$ with $C'$ a constant depending on $\Gamma$. Then, when $|x| \le N_0$, we obtain $|u(x) - u_\infty| \le 2U \le 2U(C'N/|x|)^{D-2}$, and so the result still holds. As $u$ is bounded below, we can look at the behavior of $u + U$ which has the same speed of convergence. Hence we can use the previous analysis for non-negative functions.

If $u$ corresponds to case 4, then $-u + U$ corresponds to case 3 and has the same speed of convergence. So we just deal with cases 2, 3.
Let $f$ be a non-negative function on $\Gamma$, sub-harmonic outside the ball $B(z, N)$ and vanishing at infinity. We denote $G_z(x)$ the Green's function rooted at $z$, i.e. the unique solution of $\Delta u = \delta_z$ which vanishes at infinity. Under (1.2) and (1.1) with exponent $D > 2$, there exists a constant $c$ such that (see [3])

for every $x \neq z$, $G_z(x) \leq c|x|^{2-D}$.

With $N_0 = C'N \in \mathbb{N}$, we denote

$$a = \min_{S(z, N_0)} G_z(x) \quad \text{and} \quad b = \max_{S(z, N_0)} f.$$

Then $(b/a)G_z \geq f$ on $S(z, N_0)$. $(b/a)G_z - f$ is a super-harmonic function therefore we can use the minimum principle. Since $(b/a)G_z - f$ vanishes at infinity and is non-negative on $S(z, N_0)$, this function remains non-negative out of $B(z, N_0)$. Otherwise it should have a local minimum, which would contradict the minimum principle. Hence for all $x \notin B(z, N_0)$,

$$f(x) \leq (b/a)G_z(x) \leq cU|x|^{2-D} \quad (3.6)$$

For case 3, $f = u_\infty - u$ is a non-negative function on $\Gamma$, sub-harmonic outside the ball $B(z, N)$ and vanishing at infinity. So, by the above argument, the claim follows. For case 2, the sign of $f = u - u_\infty$ may change since $M(r)$ is decreasing and $m(r)$ is increasing, both tending to $u_\infty$ at infinity. We denote $f_1 = \max(0, f)$ and $f_2 = \max(0, -f)$. These are non-negative functions and we easily see that they are sub-harmonic outside $B(z, N)$. As they vanish at infinity, we obtain (3.6) for $f_1$ and $f_2$ and the result is also true. $\square$

*Example:* Let $S^x(k)$ be the simple random walk on $\Gamma$ started at $x$, and $\tau_{B(z,N)}$ be the hitting time of $B(z, N)$. Then, the function $u(x) = P^x\{\tau_{B(z,N)} < \infty\}$ is harmonic outside $B(z, N)$, bounded by 1 and tends to 0 when $|x|$ goes to infinity. Then Theorem 3.2 gives

$$P^x\{\tau_{B(z,N)} < \infty\} \leq c(|x|/N)^{2-D}.$$

## 3.1 Poincaré-type inequality on annuli

Here, $\Gamma$ is the Cayley graph of a finitely generated group $G$, associated with a symmetric finite generating set $S$: its vertices are the elements of $G$, and
there is an edge between $x$ and $y$ when $yx^{-1} \in S$. We assume the polynomial volume growth (1.1), then (see [1, 7]) $\Gamma$ satisfies (1.2), and so the relative connectedness of the spheres. On this kind of graph, the proof of the Poincaré-type inequality on balls relies on the construction of a particular path $\gamma_{x,y}$ between each pair of vertices $x, y$ in a ball $B(z, R)$ ($z \in \Gamma$, $R > 0$). The set of these paths should have the property to pass “not too often” through any edge in $B(z, 2R)$. To obtain the same type of inequality on annuli we will need to define the path $\gamma_{x,y}$ in a way adapted to our setting. Recall the constants $\alpha$ and $R_0$ from Theorem 2.1. The Poincaré-type inequalities on annuli are the following.

**Theorem 3.3** Let $\Gamma$ be the Cayley graph of a group with polynomial volume growth of exponent $D > 1$. Then, for all $p \ge 1$, there exists a constant $C(p)$ such that for all $z \in \Gamma$, $s, t \in \mathbb{N}$ ($t \ge s \ge R_0$), and any function $f$ on $\Gamma$, we have

$$ \sum_{y \in A(z,s,t)} |f(y) - f_{A(z,s,t)}|^p \le C(p)(t/s)^{D_p} s^p \sum_{y \in A(z, \alpha^{-1}s/3, \alpha t + 2\alpha^{-1}s/3)} |\nabla f(y)|^p. $$

**PROOF:** As before, we omit the reference to the center $z$ of the annuli. We cover the annulus $A(\alpha^{-1}s, \alpha t)$ by a minimal number $I$ of balls $B_i = B(v_i, \alpha^{-1}s/6)$ such that all the $B(v_i, \alpha^{-1}s/12)$ are disjoint. We denote $B = \{B_i : 1 \le i \le I\}$ this covering. Then,

$$ \sum_{i=1}^{I} \#B(v_i, \alpha^{-1}s/12) \le \#A(3\alpha^{-1}s/4, \alpha t + \alpha^{-1}s/4), $$

which leads, as in Proposition 2.2, to $I \le c(t/s)^D$. Let $N_i$ be the number of balls intersected by $B_i$. Let us denote them $B(v_{i_k}, \alpha^{-1}s/6)$ ($k = 1$ to $N_i$). Remark that

$$ \bigcup_{k=1}^{N_i} B(v_{i_k}, \alpha^{-1}s/6) \subset B(v_i, \alpha^{-1}s/2), $$

and, as all the $B(v_{i_k}, \alpha^{-1}s/12)$ are disjoint,

$$ \sum_{k=1}^{N_i} \#B(v_{i_k}, \alpha^{-1}s/12) \le \#B(v_i, \alpha^{-1}s/2). $$

So the $N_i$'s are bounded by say $N$, which does not depend on $s$ nor $t$.
Let $x, y \in A(s, t)$. We construct a path from $x$ to $y$ in the spirit of [4, Ex. 2.3]. By Theorem 2.1, there is a path $\gamma$ from $x$ to $y$ within $A(\alpha^{-1}s, \alpha t)$. We define an index $i(x)$ associated to $x$:

$$i(x) = \inf \left\{ i : d(v_i, x) = \min_j d(v_j, x) \right\}$$

We remark that $x \in B_{i(x)}$. Likewise, we define $i(y)$.

The path $\gamma$ intersects a sequence of $B_i$'s denoted $B_{i(k)}$ ($k = 0$ to $K$) and we can take $i(0) = i(x)$ and $i(K) = i(y)$ (adding $B_{i(x)}$ and $B_{i(y)}$ to the sequence if necessary). We first construct a sequence of vertices ($z_n$) ($n = 0$ to $2K + 1$), from $x$ to $y$ as follows

$$z_{2k} = v_{i(k)} v_{i(x)}^{-1} x \quad \text{and} \quad z_{2k+1} = v_{i(k)} v_{i(y)}^{-1} y. \qquad (3.7)$$

We denote $3B_{i(k)} = B(v_{i(k)}, \alpha^{-1}s/2)$ and $5B_{i(k)} = B(v_{i(k)}, 5\alpha^{-1}s/6)$. For all $k$, $z_{2k}$ and $z_{2k+1}$ belong to $B_{i(k)}$ and $z_{2k+2}$ belongs to $3B_{i(k)}$. So, for all $n$, $d(z_n, z_{n+1}) \le 2\alpha^{-1}s/3$. Let $g(z_n^{-1}z_{n+1})$ be a minimal path from $e$ to $z_n^{-1}z_{n+1}$. We join $z_n$ and $z_{n+1}$ by the translated path $z_n g(z_n^{-1}z_{n+1})$ which stays within $5B_{i([n/2])}$ (where $[$ denotes the integer part). Finally, we obtain a path $\gamma_{x,y}$ from $x$ to $y$ within $A' = A(\alpha^{-1}s/6, \alpha t + 5\alpha^{-1}s/6)$, whose length is bounded by $Cs(t/s)^D$ for some non-negative constant $C$. Indeed,

$$(\text{length of } \gamma_{x,y}) \le \sum_{n=0}^{2K} d(z_n, z_{n+1}) \le 4I\alpha^{-1}s/3 \le Cs(t/s)^D.$$

Now, we prove our Poincaré-type inequality using the same technique as the one on balls (see [1, 7]). We denote $H(a, b) = \# \{\{x, y\} : (a, b) \in \gamma_{x,y}\}$, where $(a, b)$ denotes the edge between two neighbors $a$ and $b$.

$$\sum_{y \in A(s,t)} |f(y) - f_{A(s,t)}|^p = \sum_{y \in A(s,t)} \left| f(y) - \frac{1}{\#A(s,t)} \sum_{x \in A(s,t)} f(x) \right|^p \\ \le \sum_{y \in A(s,t)} \left( \frac{1}{\#A(s,t)} \sum_{x \in A(s,t)} |f(y) - f(x)| \right)^p \\ \le \frac{1}{\#A(s,t)} \sum_{x,y \in A(s,t)} |f(y) - f(x)|^p$$
$$
\begin{align*}
&\le C t^{-D} \sum_{x,y \in A(s,t)} (\text{length of } \gamma_{x,y})^{p-1} \sum_{(a,b) \in \gamma_{x,y}} |f(a) - f(b)|^p \\
&\le C t^{-D} s^{p-1} (t/s)^{D(p-1)} \sum_{(a,b) \in A'} |f(a) - f(b)|^p H(a, b) \\
&\le C t^{-D} s^{p-1} (t/s)^{D(p-1)} \sup_{(a,b) \in A'} H(a, b) \sum_{a \in A'} |\nabla f(a)|^p.
\end{align*}
$$

To estimate $H(a, b)$, let first write

$$
H(a, b) = \sum_{i=1}^{I} \sum_{j=1}^{I} \# \{ \{x, y\} \in A(s, t) : i(x) = i, i(y) = j, (a, b) \in \gamma_{x,y} \}
$$

Now, suppose $i$ and $j$ fixed. We want to bound the number of pair of vertices $\{x, y\}$ such that $i(x) = i$, $i(y) = j$ and $(a, b) \in \gamma_{x,y}$. Saying that the edge $(a, b)$ belongs to $\gamma_{x,y}$ means that $(a, b)$ belongs to one of the paths $z_n g(z_n^{-1} z_{n+1})$ defined above.

We need to obtain a bound $K_1$ for the number of balls in $\mathcal{B}$ that could contain such $z_n$, and likewise, a bound $K_2$ for the number of balls in $\mathcal{B}$ that could contain such $z_{n+1}$. Then, we want a bound $K_3$ for the number of elements $h \in \Gamma$ such that $h = z_n^{-1} z_{n+1}$. Finally, we need a bound $K_4$ for the number of possible $z_n$. By (3.7), $v_i([n/2])$, $v_i([[(n+1)/2]])$, $z_n$, $z_{n+1}$, $i = i(x)$ and $j = i(y)$ fully determine the pair $\{x, y\}$, so

$$
H(a, b) \le I^2 K_1 K_2 K_3 K_4. \tag{3.8}
$$

Since $g(z_n^{-1}z_{n+1})$ has length less than $2\alpha^{-1}s/3$, the vertices $a$ and $b$ should be
at distance less than $5\alpha^{-1}s/6$ from the center of any ball in $\mathcal{B}$ that contains
such $z_n$. By definition of the overlapping bound $N$, for a fixed edge $(a, b)$,
there are at most $(N+1)^5$ such balls. So, $K_1 \le (N+1)^5$ and likewise $K_2 \le$
$(N+1)^5$. As $z_n^{-1}z_{n+1} \in B(e, \alpha^{-1}s/3)$, there are, at most, $\#B(e, \alpha^{-1}s/3)$
choices for $z_n^{-1}z_{n+1}$, so $K_3 \le C_s^D$. Once $z_n^{-1}z_{n+1}$ is fixed, knowing that $(a, b)$
is one of the edges of $z_n g(z_n^{-1}z_{n+1})$ leaves $d(z_n, z_{n+1}) \le 2\alpha^{-1}s/3$ choices for
the starting point $z_n$, so $K_4 \le 2\alpha^{-1}s/3$.

Finally, plugging these bounds and $I \le c(t/s)^D$ into (3.8), we obtain

$$
H(a, b) \leq C I^2 N^{10} s^{D+1} \leq C (t/s)^{2D} s^{D+1}.
$$

Therefore, the result follows.

**Acknowledgment:** I am very grateful to L. Saloff-Coste for his great help during all the preparation of this manuscript. I also thank T. Coulhon and T. Delmotte for useful remarks.

<figure><img src="image_1.png" /></figure>
References

[1] T. Coulhon and L. Saloff-Coste, *Isopérimétrie pour les groupes et les variétés*, Rev. Mat. Iberoamericana **9** (1993), no. 2, 293-314.

[2] T. Delmotte, *Inégalité de Harnack elliptique sur les graphes*, Colloquium Mathematicum **80** (1997), no. 1, 19-37.

[3] T. Delmotte, *Parabolic Harnack inequality and estimates of Markov chains on graphs*, Rev. Mat. Iberoamericana **15** (1999), no. 1, 181-232.

[4] P. Diaconis and L. Saloff-Coste, *Comparison theorems for reversible Markov chains*, Ann. Appl. Probab. **3** (1993), no. 3, 696-730.

[5] P. Hajlasz and P. Koskela, *Sobolev met Poincaré*, Mem. Amer. Math. Soc. **145** (2000), no. 688, x+101.

[6] J. Moser, *On Harnack's theorem for elliptic differential equations*, Comm. Pure and Applied Math. **14** (1961), 577-591.

[7] L. Saloff-Coste, *Isoperimetric inequalities and decay of iterated kernels for almost-transitive Markov chains*, Combin. Probab. Comput. **4** (1995), 419-442.

SÉBASTIEN BLACHÈRE
LSP, UNIVERSITÉ PAUL SABATIER
AND DMA, ÉCOLE POLYTECHNIQUE
FÉDÉRALE DE LAUSANNE
ECUBLENS
1015 LAUSANNE
SUISSE
sebastien.blachere@epfl.ch