Annales Academiæ Scientiarum Fennicæ Mathematica Volumen 22, 1997, 205–226

A STRONG LIOUVILLE THEOREM FOR p-HARMONIC FUNCTIONS ON GRAPHS

Ilkka Holopainen and Paolo M. Soardi

University of Helsinki, Department of Mathematics P.O. Box 4, FIN-00014 Helsinki, Finland; ih@geom.helsinki.fi Università di Milano, Dipartimento di Matematica via C. Saldini 50, I-20133 Milano, Italy; soardi@vmimat.mat.unimi.it

Abstract. We prove a global Harnack inequality for positive p-harmonic functions on a graph Γ provided a weak Poincaré inequality holds on Γ and the counting measure of Γ is doubling. Consequently, every positive p-harmonic function on such a graph must be constant.

1. Introduction

Harmonic functions on graphs and on other discrete structures are interesting not only for their own sake but also because they are closely related to harmonic functions on noncompact Riemannian manifolds. For instance, if the local geometry of M is controlled, then the parabolicity of M, i.e. the nonexistence of Green’s function on M, is characterized by the parabolicity of certain discrete structures, called ε-nets, of M. Furthermore, M has nonconstant harmonic functions of finite energy if and only if any ε-net of M does so. Analogous statements hold also in the case of p-harmonic functions. Recall that an ε-net of M is a graph whose vertex set X is a maximal ε-separated subset of M, with a fixed constant ε > 0, and whose edge set consists of all (unoriented) pairs x, y ∈ X such that 0 < d(x, y) ≤ 3ε, where d stands for the Riemannian distance. Above x and y are also said to be neighbors. Furthermore, a real-valued function on X is harmonic if and only if its value at each point x ∈ X is the average of its values at the neighbors of x. We refer to [V1], [K2], [H2], and [HS] for the proofs and precise formulations of the above statements. In [LS] Lyons and Sullivan considered a slightly different discretization of a manifold M. We mention here just one result among the many in [LS]. It states that, for certain discrete sets X ⊂ M and for all y ∈ M, there are positive probability measures ν_{y} on X such that every bounded harmonic function h on M satisfies h(y) = ∑_{x∈X} ν_{y}(x)h(x) at every y ∈ M. In particular, the formula holds for every y ∈ X, and so h | X is harmonic with respect to the discrete time Markov process with ν_{y}(x) as the transition probability that a particle at y ∈ X jumps next to x ∈ X. The condition for X is, roughly speaking, that each x ∈ X has neighborhoods V (x) ⋐ M and U(x) ⋐ V (x) such that ⋃_{x∈X} U(x) “almost” covers M and that a Harnack inequality sup_{U(x)} h ≤ C inf_{U(x)} h holds for every x ∈ X with a uniform constant C whenever h is a positive harmonic function in V (x). In the case where M = ⋃_{x∈X} U(x), a similar description holds for all positive harmonic functions on M. See [LS, Theorems 5 and 6] for more details. We do not know whether the above results of Lyons and Sullivan have counterparts in the nonlinear case of p-harmonic functions. It is worth pointing out that the notion of harmonicity with respect to the discrete process slightly differs from that on graphs.

1991 Mathematics Subject Classification: Primary 31C20, 31C45.

The first author was supported partly by the EU HCM contract No. CHRX-CT92-0071.

In this paper we study the existence of positive nonconstant harmonic and, in general, p-harmonic functions on graphs. Adapting the common terminology we say that a graph Γ is strong Liouville (respectively p-strong Liouville) if every positive harmonic (respectively p-harmonic) function on Γ is constant. A simple example of strong Liouville graphs is the n-dimensional grid Z^{n}. The purpose of this paper is to show that a graph Γ is p-strong Liouville under very weak conditions, more precisely, provided the counting measure of Γ is doubling and a weak Poincaré-type inequality holds on Γ. The result is obtained by proving a global Harnack inequality for positive p-harmonic functions on such a graph. It is worth noting that probabilistic methods which are naturally present in the case of harmonic functions are no longer available in the case p ≠ 2. The assumptions on Γ are in a sense sharp. Indeed, we show by examples that neither the doubling condition nor the Poincaré inequality alone implies the strong Liouville.

Throughout the paper we assume that Γ = (V, E) is an infinite connected graph, with V as the vertex set and E as the edge set. Vertices x and y are called neighbors, denoted by x ∼ y, if there is an edge between them. The degree of x, deg(x), is the number of all neighbors of x. For x, y ∈ V , the distance δ(x, y) will be the minimum number of edges which are needed to connect x and y by a chain x ∼ x_{1} ∼ ⋯ ∼ y. The cardinality of U ⊂ V will be denoted by |U|. The boundary of U, denoted by ∂U, is the set of all vertices in V \ U which have at least one neighbor in U, in brief ∂U = {x ∈ V : δ(x, U) = 1}. The set of all edges with at least one endpoint in U will be denoted by E(U).

Let u be a real-valued function in U ∪ ∂U. For each 1 < p < ∞, we set

Δ_{p}u(x) = ∑_{y∼x} sign(u(y)−u(x))|u(y)−u(x)|^{p−1} = ∑_{y∼x} |u(y)−u(x)|^{p−2}(u(y)−u(x)),

where we make a convention that |u(y)−u(x)|^{p−2}(u(y)−u(x)) = 0 if u(y) = u(x)

also in case 1 < p < 2. We also set |∇_{p}u(x)| = (∑_{y∼x} |u(y)−u(x)|^{p})^{1/p} for p ≥ 1.

1.1. Definition. A function u of U ∪ ∂U is called p-harmonic (p-superhar-monic) in U if Δ_{p}u(x) = 0 (respectively Δ_{p}u(x) ≤ 0) at every point x ∈ U.

A strong Liouville theorem for p-harmonic functions on graphs 207

Equivalently, u is p-harmonic (or p-superharmonic) in U if and only if

(1.2) ∑_{x∈U} ∑_{y∼x} |u(y) − u(x)|^{p−2}(u(y) − u(x))(w(y) − w(x)) = 0  (or ≥ 0)

for every finitely supported test function w in U ∪ ∂U, with w = 0 in ∂U and, in addition, w ≥ 0 in the case of p-superharmonic functions; see [HS]. In the special case p = 2, we obtain harmonic (respectively superharmonic) functions.

If B = B(y, r) = {x ∈ V : δ(x, y) ≤ r} is a ball and t > 0, we write tB = B(y, tr). Observe that given a ball B, its center and radius need not be unique. When we write B and tB, we assume that a radius and a center of B are fixed or clear from the context. Most of the time we assume that Γ satisfies the following two conditions.

1. The (counting) measure |·| is doubling, i.e., there exists a (doubling) constant C_{d} such that

(D)  |B(y, 2r)| ≤ C_{d}|B(y, r)|

for every ball B(y, r) ⊂ V .

2. A weak (1, p)-Poincaré inequality holds, i.e., there are constants c and t ≥ 1 such that, for every ball B = B(y, r),

(P_{p})  \frac{1}{|B|} ∑_{x∈B} |u(x) − u_{B}| ≤ cr(\frac{1}{|tB|} ∑_{x∈tB} |∇_{p}u(x)|^{p})^{1/p}

whenever u is a function in tB ∪ ∂(tB).

Here and from now on u_{B} = |B|^{−1} ∑_{x∈B} u(x) is the average of u in B. An immediate consequence of (D) is that Γ is of bounded degree, i.e.,

(1.3)  d = sup{deg(x) : x ∈ V } < ∞.

The constant d will be called the maximum degree of Γ. Indeed, applying (D) with r = \frac{1}{2} yields d ≤ C_{d} − 1. In [HK] Hajłasz and Koskela proved in a very general setting of metric spaces that the doubling condition and a Poincaré inequality imply a Sobolev–Poincaré inequality; see also [SC1]. In particular, their results apply to graphs and so we have the following lemma.

1.4. Lemma. Suppose that Γ satisfies assumptions (D) and (P_{p}). Then there are constants λ > 1 and c such that, for every ball B = B(y, r) ⊂ V ,

(1.5)  (\frac{1}{|B|} ∑_{x∈B} |u(x) − u_{B}|^{λp})^{1/(λp)} ≤ cr(\frac{1}{|B|} ∑_{x∈B} |∇_{p}u(x)|^{p})^{1/p}

whenever u is a function in B ∪ ∂B.

As a consequence of (1.5) we have

(1.6)  (\frac{1}{|B|} ∑_{x∈B} |v(x)|^{λp})^{1/(λp)} ≤ cr(\frac{1}{|B|} ∑_{x∈B} |∇_{p}v(x)|^{p})^{1/p}

for every v vanishing in ∂B, and

(1.7)  (\frac{1}{|B|} ∑_{x∈B} |u(x) − u_{B}|^{p})^{1/p} ≤ cr(\frac{1}{|B|} ∑_{x∈B} |∇_{p}u(x)|^{p})^{1/p}

whenever u is a function in B ∪ ∂B.

Throughout the paper we say that u is positive and p-harmonic in U if it is positive in U ∪ ∂U and p-harmonic in U. The main results of the paper are the following.

1.8. Theorem. Suppose that Γ satisfies (D) and (P_{p}). Then there is a constant C_{1} such that

(1.9)  max_{x∈B} u(x) ≤ C_{1} min_{x∈B} u(x)

whenever u is a positive p-harmonic function in 6B ⊂ V and B = B(o, 2^{N}).

1.10. Corollary. Suppose that Γ satisfies assumptions (D) and (P_{p}). Then Γ is p-strong Liouville.

Corollary 1.10 follows easily from Harnack’s inequality. Indeed, suppose that u is a positive nonconstant p-harmonic function on V . We may assume that inf_{V} u = 0. By the Harnack inequality (1.9)

max_{B(o,2^{N})} u ≤ C_{1} min_{B(o,2^{N})} u,

where the right hand side tends to zero as N → ∞. Hence u is constant, which leads to a contradiction.

1.11. Corollary. Suppose that Γ satisfies (D) and (P_{1} ), i.e. a weak (1, 1)- Poincaré inequality. Then Γ is p-strong Liouville for every p > 1.

Corollary 1.11 holds since a (1, q)-Poincaré inequality implies a (1, p)-Poin-caré inequality for every p ≥ q by Hölder’s inequality. On the other hand, given p > q ≥ 1 it is possible to construct graphs which admit the (1, p)-Poincaré inequality but not the (1, q)-Poincaré inequality. These constructions can be done by using ideas from [HeK]; we thank J. Heinonen for pointing out this to us.

We prove Theorem 1.11 by using a Moser-type iteration. Inequalities (1.6) and (1.7) are crucial in the iteration process. In addition to these we need a Caccioppoli-type inequality (Theorem 2.1) and a version of the John–Nirenberg lemma (Lemma 3.8). The Moser iteration may be a too complicated method in the discrete setting. It would be interesting to find a simpler proof for the Harnack inequality by scrutinizing directly the equation Δ_{p}u(x) = 0. On the other hand, our assumptions on the graph are quite minimal.

Throughout the paper C_{d} will refer to the doubling constant, c will be a positive constant whose value may change even within a line, and c(a, b, …) denotes a constant depending on a, b, . . ..

In addition to the references given at the beginning of the introduction, we refer to [A], [B], [BS], [L], [MMT], [RSV], [S1], and [S2] for further studies on discrete potential theory and, in particular, for Liouville-type results on graphs. For the nonlinear potential theory in R^{n} and on Riemannian manifolds we refer to [HKM] and [H1]. After the paper was completed T. Coulhon informed us about the manuscript [De] where a global Harnack inequality is proved for positive harmonic functions on graphs assuming the graph satisfies the doubling condition and a Poincaré inequality. We also received a manuscript [SC3], where Saloff-Coste studied Harnack inequalities for p-harmonic functions on networks. He obtained a global Harnack inequality if the network has at most quadratic volume growth and only one end in a very strong sense.

Acknowledgement. We wish to thank J. Kinnunen for discussions concerning the John–Nirenberg lemma.

2. Caccioppoli-type inequality

This section is devoted to a Caccioppoli-type inequality for p-harmonic functions. Here the assumptions (D) and (P_{p}) are not needed. Instead we assume that Γ is of bounded degree. Occasionally we fix an orientation in the edge set and write x⃗y for an oriented edge from x to y. In particular, for a given function u in V , we sometimes choose the orientation such that either

(O1)  u(x) ≥ u(y) for every x⃗y,

or

(O2)  u(y) ≥ u(x) for every x⃗y.

Recall from the introduction that E(U) stands for the set of all edges with at least one endpoint in U ⊂ V . The Caccioppoli inequality (2.2) and its consequence (2.13) are discrete counterparts of the corresponding inequalities for positive pharmonic functions in R^{n}; see e.g. [HKM] and [H1].

2.1. Theorem. Let u be positive and p-harmonic in U, and let q ∈ R \ {p − 1}. Then there exists a constant c = c(p, d) such that

(2.2) \begin{matrix}∑_{x⃗y∈E(U)} & |u(y) − u(x)|^{p}(u^{q−p}(y) + u^{q−p}(x))(η^{p}(x) + η^{p}(y)) \\ ≤ c max\{|q − p + 1|^{−p}, 1\} ∑_{x⃗y∈E(U)}(u^{q}(x) + u^{q}(y))|η(y) − η(x)|^{p} \end{matrix}

for any nonnegative finitely supported function η in U ∪ ∂U, with η(x) = 0 if δ(x, ∂U) ≤ 1.

The constant c above depends on the maximum degree since we shall apply the following local Harnack inequality from [HS] during the proof.

2.3. Lemma. Let u be nonnegative in U ∪ ∂U and p-superharmonic in U. Then, for each x ∈ U, we have

(2.4)  max_{y∼x} u(y) ≤ cu(x),  with c = deg(x)^{1/(p−1)} + 1.

In particular, (2.4) holds with a constant C_{0} = d^{1/(p−1)} + 1, where d is the maximum degree.

Proof of 2.1. Let η be as in the claim. Set φ = u^{κ}η^{p}, where κ = q − p + 1 and q ∈ R \ {p − 1}. Then

φ(y) − φ(x) = η^{p}(x)(u^{κ}(y) − u^{κ}(x)) + u^{κ}(y)(η^{p}(y) − η^{p}(x)).

Using φ as a test function in (1.2) we obtain

(2.5) \begin{matrix}∑_{x∈U} ∑_{y∼x} & |u(y) − u(x)|^{p−2}(u(y) − u(x))η^{p}(x)(u^{κ}(x) − u^{κ}(y)) \\ = ∑_{x∈U} ∑_{y∼x} |u(y) − u(x)|^{p−2}(u(y) − u(x))u^{κ}(y)(η^{p}(y) − η^{p}(x)). \end{matrix}

Choose either the orientation (O1) or (O2). Then (2.5) reads as

\begin{matrix}∑_{x⃗y∈E(U)} & |u(y) − u(x)|^{p−1}(η^{p}(x) + η^{p}(y))(u^{κ}(x) − u^{κ}(y)) \\ = ∑_{x⃗y∈E(U)} |u(y) − u(x)|^{p−1}(u^{κ}(y) + u^{κ}(x))(η^{p}(y) − η^{p}(x)). \end{matrix}

On the other hand,

η^{p}(y) − η^{p}(x) = p ∫_{η(x)}^{η(y)} t^{p−1} dt ≤ p(η^{p−1}(y) + η^{p−1}(x))|η(y) − η(x)|.

Hence

(2.6)  \begin{matrix}∑_{x⃗y∈E(U)} |u(y) − u(x)|^{p−1}(η^{p}(x) + η^{p}(y))(u^{κ}(x) − u^{κ}(y)) \\ ≤ p ∑_{x⃗y∈E(U)} |u(y) − u(x)|^{p−1}(u^{κ}(y) + u^{κ}(x))× \\ × (η^{p−1}(y) + η^{p−1}(x))|η(y) − η(x)|. \end{matrix}

To estimate the left hand side of (2.6) from below we write

\begin{aligned}u^{κ}(x) & − u^{κ}(y) = (u^{κ−1}(y) + u^{κ−1}(x))(u(x) − u(y)) + u^{κ−1}(x)u(y) − u^{κ−1}(y)u(x) \\ & = (u^{q−p}(y) + u^{q−p}(x))(u(x) − u(y)) + u(x)u(y)(u^{κ−2}(x) − u^{κ−2}(y)). \end{aligned}

Observe that it suffices to take the sums on both sides of (2.6) over the edges x⃗y with both endpoints in U since otherwise η(x) = η(y) = 0. Therefore we assume to the end of the proof that x, y ∈ U and x ∼ y. Suppose first that κ ≥ 2 and choose the orientation (O1), i.e. u(x) ≥ u(y) for all x⃗y. Then

(2.7)  u^{κ}(x) − u^{κ}(y) ≥ (u^{q−p}(y) + u^{q−p}(x))(u(x) − u(y)).

Let then 1 ≤ κ < 2 and choose again the orientation (O1). We want an estimate

\begin{matrix}(u^{κ−1}(y)+ & u^{κ−1}(x))(u(x) − u(y)) + u(x)u(y)(u^{κ−2}(x) − u^{κ−2}(y)) \\ ≥ c(u^{κ−1}(y) + u^{κ−1}(x))(u(x) − u(y)), \end{matrix}

or equivalently

(2.8) u^{κ−2}(y) − u^{κ−2}(x) ≤ (1 − c))(u^{κ−1}(y) + u^{κ−1}(x))(u^{−1}(y) − u^{−1}(x)),

where c is some positive constant. Set β = u^{−1}(y) and α = u^{−1}(x). Then (2.8) reads as

β^{2−κ} − α^{2−κ} ≤ (1 − c))(β^{1−κ} + α^{1−κ})(β − α).

This estimate holds with c = \frac{1}{2} since

β^{2−κ} − α^{2−κ} = (2 − κ) ∫_{α}^{β} t^{1−κ} dt
≤ (2 − κ)[β^{1−κ}(β − α) + \frac{1}{2}(α^{1−κ} − β^{1−κ})(β − α)]
≤ \frac{1}{2}(α^{1−κ} + β^{1−κ})(β − α).

The estimate above holds since the curve (t, t^{1−κ}), with α ≤ t ≤ β, lies below the line segment between points (α, α^{1−κ}) and (β, β^{1−κ}). Hence, for 1 ≤ κ < 2,

(2.9)  u^{κ}(x) − u^{κ}(y) ≥ \frac{1}{2}(u^{q−p}(y) + u^{q−p}(x))(u(x) − u(y)).

Suppose next that 0 < κ < 1 and choose again the orientation (O1). If u(x) ≥ u(y), then u^{κ}(x) ≥ u^{κ}(y), u(x) ≤ C_{0}u(y) by (2.4), and so

u^{κ−1}(x) = \frac{u^{κ}(x)}{u(x)} ≥ \frac{u^{κ}(y)}{C_{0}u(y)} = \frac{1}{C_{0}} u^{κ−1}(y).

Hence

(2.10)  \begin{aligned}u^{κ}(x) − u^{κ}(y) & = κ ∫_{u(y)}^{u(x)} t^{κ−1} dt ≥ κu^{κ−1}(x)(u(x) − u(y)) \\ & ≥ \frac{κ}{2C_{0}} (u^{q−p}(x) + u^{q−p}(y))(u(x) − u(y)). \end{aligned}

Finally, suppose that κ < 0 and choose the orientation (O2). Now the local Harnack inequality (2.4) and the estimates (2.7), (2.9), and (2.10) imply that

u^{κ}(x) − u^{κ}(y) = u^{κ}(x)u^{κ}(y)u(u^{−κ}(y) − u^{−κ}(x))

≥ u^{κ}(x)u^{κ}(y)c(κ)(u^{−κ−1}(y) + u^{−κ−1}(x))(u(y) − u(x))

= c(κ)(\frac{u(x)}{u(y)}u^{κ−1}(x) + \frac{u(y)}{u(x)}u^{κ−1}(y))(u(y) − u(x))

≥ \frac{c(κ)}{C_{0}}(u^{q−p}(x) + u^{q−p}(y))(u(y) − u(x))

since u(x)/u(y) ≥ 1/C_{0} and u(y)/u(x) ≥ 1/C_{0} . Above

c(κ) = \{ \begin{matrix}\frac{1}{2} & if κ ≤ −1; \\ −κ/(2C_{0}) & if −1 < κ < 0. \end{matrix}

We have proved

(2.11) \begin{matrix}∑_{x⃗y∈E(U)} & |u(y) − u(x)|^{p}(u^{q−p}(y) + u^{q−p}(x))(η^{p}(x) + η^{p}(y)) \\ ≤ c_{1}(κ) ∑_{x⃗y∈E(U)} |u(y) − u(x)|^{p−1}(η^{p}(x) + η^{p}(y))(u^{κ}(x) − u^{κ}(y)) \end{matrix}

for all κ ≠ 0, where the orientation is (O1) if κ > 0 and (O2) if κ < 0. Combining this with (2.6) and using Hölder’s inequality we obtain

∑_{x⃗y∈E(U)} |u(y) − u(x)|^{p}(u^{q−p}(y) + u^{q−p}(x))(η^{p}(x) + η^{p}(y))

≤ pc_{1}(κ)( ∑_{x⃗y∈E(U)}(u^{q}(x) + u^{q}(y))|η(y) − η(x)|^{p})^{1/p}×

× ( ∑_{x⃗y∈E(U)} |u(y) − u(x)|^{p}(u^{q−p}(y) + u^{q−p}(x))(η^{p}(x) + η^{p}(y)))^{(p−1)/p}.

Hence

\begin{matrix}∑_{x⃗y∈E(U)} & |u(y) − u(x)|^{p}(u^{q−p}(y) + u^{q−p}(x))(η^{p}(x) + η^{p}(y)) \\ ≤ (c_{2}(κ))^{p} ∑_{x⃗y∈E(U)}(u^{q}(x) + u^{q}(y))|η(y) − η(x)|^{p}, \end{matrix}

where c_{2}(κ) = c max{1/|κ|, 1}, with c = c(p, d). Observe that the final inequality is independent of the orientation. The theorem is proved.

Theorem 2.1 with q = 0 and an elementary fact

| log u(x) − log u(y)| ≤ (u^{−1}(x) + u^{−1}(y))|u(x) − u(y)|

imply the next Corollary.

2.12. Corollary. Let S ⊂ U be finite such that δ(∂S, ∂U) ≥ 2. Suppose that u is positive and p-harmonic in U. Then there exists a constant c = c(p, d) such that

(2.13)  ∑_{x∈S} |∇_{p} log u(x)|^{p} ≤ c ∑_{x⃗y∈E(U)} |η(y) − η(x)|^{p}

whenever η is a nonnegative finitely supported function in U ∪ ∂U, with η = 1 in S ∪ ∂S and η(x) = 0 if δ(x, ∂U) ≤ 1.

We call Γ p-parabolic if

inf_{η} ∑_{x∈V} |∇_{p}η(x)|^{p} = 0,

where the infimum is taken over all finitely supported functions η, with η(o) = 1 for some fixed o ∈ V . Corollary 2.12 gives a proof for the following well-known result. The details are left to the reader.

2.14. Corollary. If Γ is p-parabolic, then it is also p-strong Liouville.

3. Global Harnack’s inequality

We start with a John–Nirenberg lemma. A function v: U → R, where U ⊂ V , is said to be in BMO(U), (bounded mean oscillation), if

∥v∥_{∗} = sup_{B} |B|^{−1} ∑_{x∈B} |v(x) − v_{B}| < ∞,

where the supremum is taken over all balls B ⊂ U. It is known that in many situations BMO is equivalent to “exponential BMO”; see e.g. [JN], [HKM, p. 336– 341], and [FS, p. 154]. Furthermore, in a footnote in [CW2, p. 594] it is stated that this equivalence holds in any metric space of homogeneous type, in particular in our setting. Since we do not know any proof for this, we feel it appropriate to study the problem more closely. Here we show the equivalence in the case U = V on graphs (V, E) satisfying the doubling condition. For general U ⊂ V we prove a local version which suffices for our purpose. Our proofs are adapted from [HKM, p. 336–341] with some changes which are mainly caused by the absence of the Besicovitch covering theorem. As a first step we observe that the doubling condition implies the following version of the Calderón–Zygmund decomposition.

3.1. Lemma. Suppose that Γ satisfies (D). Let f be a nonnegative function in a ball B = B(o, R) ⊂ V and let α ≥ |B|^{−1} ∑_{x∈B} f(x). Then there are disjoint balls B_{i} = B(x_{i}, r_{i}) ⊂ B and a constant c_{0} = c_{0}(C_{d}) ≥ 1 such that

(3.2)  f(x) ≤ α for x ∈ B \ ⋃_{i} 5B_{i},
(3.3)  α < |B_{i}|^{−1} ∑_{x∈B_{i}} f(x) ≤ c_{0}α,

and

(3.4)  ∑_{i} |5B_{i}| ≤ \frac{C_{d}^{3}}{α} ∑_{x∈B} f(x).

If, in addition, α > C_{d}^{6}|B|^{−1} ∑_{x∈B} f(x), then r_{i} < R/20 for every i.

Proof. For all x ∈ B one first constructs a sequence of balls B_{i}^{x} ⊂ B, i = 0, 1, …, such that

B = B_{0}^{x} ⊃ B_{1}^{x} ⊃ B_{2}^{x} ⊃ ⋯ ∋ x, B_{i}^{x} = {x} for i ≥ i_{x},

and that |B_{i−1}^{x}|/|B_{i}^{x}| ≤ c_{0} , with a constant c_{0} = c_{0}(C_{d}). Such a construction can easily be done on graphs. Next we set

E_{α} = {x ∈ B : f(x) > α}.

For each x ∈ E_{α}, there is a unique k = k_{x} ≥ 1 such that

|B_{k}^{x}|^{−1} ∑_{y∈B_{k}^{x}} f(y) > α

but

|B_{i}^{x}|^{−1} ∑_{y∈B_{i}^{x}} f(y) ≤ α for all i ≤ k − 1.

The balls B_{k}^{x}, x ∈ E_{α}, cover E_{α} and by a Vitali type covering lemma (cf. e.g. [CW1, Theorem (1.2)]) we may find a (finite) subfamily of mutually disjoint balls B_{i} ∈ {B_{k}^{x} : x ∈ E_{α}} such that E_{α} ⊂ ⋃_{i} 5B_{i}. For any ball B_{i} = B_{k}^{x} we then have

(3.5)  α < |B_{i}|^{−1} ∑_{y∈B_{i}} f(y) ≤ (|B_{k−1}^{x}||B_{k}^{x}|^{−1})|B_{k−1}^{x}|^{−1} ∑_{y∈B_{k−1}^{x}} f(y) ≤ c_{0}α.

Thus (3.3) is established. Since ⋃_{i} 5B_{i} covers E_{α}, the condition (3.2) holds. Furthermore, the doubling condition, (3.5), and the disjointness of balls B_{i} imply (3.4) since

∑_{i} |5B_{i}| ≤ C_{d}^{3} ∑_{i} |B_{i}| ≤ C_{d}^{3} ∑_{i} α^{−1} ∑_{y∈B_{i}} f(y) ≤ \frac{C_{d}^{3}}{α} ∑_{y∈B} f(y).

To prove the last statement, fix α > C_{d}^{6}|B|^{−1} ∑_{x∈B} f(x) and suppose that r_{i} ≥ R/20 for some i. Since B_{i} ⊂ B, we observe that B ⊂ 40B_{i}. We get a contradiction, since

|B| ≤ C_{d}^{3}|5B_{i}| ≤ \frac{C_{d}^{6}}{α} ∑_{x∈B} f(x) < |B|,

by the doubling condition and (3.4). The lemma is proved.

It is convenient for our later purpose to define

(3.6)  ∥v∥_{∗,loc} = sup_{3B⊂U} |B|^{−1} ∑_{x∈B} |v(x) − v_{B}|

whenever v is a function in U. The reason why we use the factor 3 here becomes apparent in Lemma 3.12. A consequence of the doubling condition is that

(3.7)  |v_{5B} − v_{B}| ≤ C_{d}^{3} ∥v∥_{∗,loc}

whenever v is a function in U and B is a ball, with 15B ⊂ U. The proof of (3.7) is easy and will be omitted.

Using Lemma 3.1 and the estimate (3.7) one can now repeat the proof in [HKM, p. 339–340] with minor changes and obtain the John–Nirenberg lemma in the following form. We remark here that the balls 5B_{i} in Lemma 3.1 need not belong entirely to B. Partly for this reason we find it appropriate to introduce (3.6) and to repeat the proof of the “only if part” of Lemma 3.8.

3.8. Lemma. Suppose that Γ satisfies (D) and that U ⊂ V . Then, for every function v: U → R, we have ∥v∥_{∗,loc} < ∞ if and only if

(3.9)  |{x ∈ B : |v(x) − v_{B}| > t}| ≤ c_{1}e^{−c_{2}t}|B|

whenever t > 0 and B is a ball with 3B ⊂ U. The constants c_{1} , c_{2} , and ∥v∥_{∗,loc} depend only on each other and C_{d}.

Proof. If (3.9) holds, then ∥v∥_{∗,loc} ≤ 2(c_{1} + 1)c_{2}^{−1} . The proof in [HKM, p. 338] applies here verbatim. To prove the “only if” part, fix a ball B such that 3B ⊂ U. We may assume that v_{B} = 0 and that ∥v∥_{∗,loc} ≤ C_{d}^{−6} . We write B(j_{1}), B(j_{1}, j_{2}), … instead of B_{j_{1}}, B_{j_{1}j_{2}}, . . .. Applying Lemma 3.1 to |v| in B with α = 2 > C_{d}^{6}|B|^{−1} ∑_{x∈B} |v(x)| we obtain disjoint balls B(j_{1}) ⊂ B such that

2 < |B(j_{1})|^{−1} ∑_{x∈B(j_{1})} |v(x)| ≤ 2c_{0},

|v(x)| ≤ 2 for x ∈ B \ ⋃_{j_{1}} 5B(j_{1}),

∑_{j_{1}} |5B(j_{1})| ≤ \frac{C_{d}^{3}}{2} ∑_{x∈B} |v(x)| ≤ \frac{1}{2C_{d}^{3}} |B| ≤ \frac{1}{2}|B|,

and that

15B(j_{1}) ⊂ (1 + 3/4)B ⊂ U.

For each j_{1} we apply Lemma 3.1 to |v − v_{5B(j_{1})}| in 5B(j_{1}) with α = 2. Observe that

C_{d}^{6}|5B(j_{1})|^{−1} ∑_{x∈5B(j_{1})} |v(x) − v_{5B(j_{1})}| < 2

since 15B(j_{1}) ⊂ U and ∥v∥_{∗,loc} ≤ C_{d}^{−6} . Now we obtain balls B(j_{1}, j_{2}) ⊂ 5B(j_{1}) such that

2 < |B(j_{1}, j_{2})|^{−1} ∑_{x∈B(j_{1},j_{2})} |v(x) − v_{5B(j_{1})}| ≤ 2c_{0},

|v(x) − v_{5B(j_{1})}| ≤ 2 for x ∈ 5B(j_{1}) \ ⋃_{j_{2}} 5B(j_{1}, j_{2}),

∑_{j_{1},j_{2}} |5B(j_{1}, j_{2})| ≤ ∑_{j_{1}} \frac{1}{2}|5B(j_{1})| ≤ (\frac{1}{2})^{2}|B|,

and that

15B(j_{1}, j_{2}) ⊂ (1 + 4^{−1} + 3/16)B ⊂ U.

The estimates above and (3.7) imply that

\begin{aligned}|v(x)| & ≤ |v(x) − v_{5B(j_{1})}| + |v_{5B(j_{1})}| ≤ 2 + |v_{B(j_{1})}| + C_{d}^{3} ∥v∥_{∗,loc} \\ & ≤ 2 + 2c_{0} + C_{d}^{−3} ≤ 2(3c_{0}) \end{aligned}

if x ∈ 5B(j_{1}) \ ⋃_{j_{2}} 5B(j_{1}, j_{2}). We continue in a similar way. At the (k + 1)st step we apply Lemma 3.1 to |v − v_{5B(j_{1},j_{2},...,j_{k})}| in 5B(j_{1}, j_{2}, …, j_{k}) with α = 2 and obtain balls B(j_{1}, …, j_{k}, j_{k+1}) ⊂ 5B(j_{1}, j_{2}, …, j_{k}) such that |v(x)| ≤ (k + 1)3c_{0} if x ∈ 5B(j_{1}, j_{2}, …, j_{k}) \ ⋃_{j_{k+1}} 5B(j_{1}, …, j_{k}, j_{k+1}), that

∑_{j_{1},...,j_{k+1}} |5B(j_{1}, …, j_{k+1})| ≤ (\frac{1}{2})^{k+1}|B|,

and that

15B(j_{1}, …, j_{k+1}) ⊂ (∑_{i=0}^{k} 4^{−i} + 3/4^{k+1})B ⊂ U.

As in [HKM, p. 340] we now deduce that (3.9) holds with c_{1} = 2 and c_{2} = (log 2)/(6c_{0}). For a general (nonconstant) function v, with ∥v∥_{∗,loc} < ∞, we obtain (3.9) with c_{1} = 2 and c_{2} = (log 2)/(6c_{0}C_{d}^{6} ∥v∥_{∗,loc}).

3.10. Corollary. Suppose that Γ satisfies (D) and that U ⊂ V . Then, for every function v: U → R, we have ∥v∥_{∗,loc} < ∞ if and only if there are constants Q and C such that

(3.11)  |B|^{−1} ∑_{x∈B} exp [Q|v(x) − v_{B}|] ≤ C

for all balls B, with 3B ⊂ U. Furthermore, if (3.11) is true, then ∥v∥_{∗,loc} ≤ C/Q. Conversely, if ∥v∥_{∗,loc} < ∞, then (3.11) holds with C = 3 and Q = (log 2)/(12c_{0}C_{d}^{6} ∥v∥_{∗}).

We shall next apply Corollary 3.10 to log u, where u is positive and pharmonic.

3.12. Lemma. Suppose that Γ satisfies (D) and (P_{p}), and that U ⊂ V . There exists a constant c depending only on p and on the constants in (D) and in (P_{p}) such that

∥log u∥_{∗,loc} ≤ c

whenever u is positive and p-harmonic in U.

Proof. Write v = log u and let B = B(o, k) ⊂ U be a ball such that 3B ⊂ U. We must show that

\frac{1}{|B|} ∑_{x∈B} |v(x) − v_{B}| ≤ c.

If k < 1, there is nothing to prove since then B(o, k) = {o}. Suppose k ≥ 1. First we observe that the doubling condition implies that card E(3B) ≤ c|B|, where E(3B) is, as before, the set of all edges with at least one end point in 3B. Next we define η: U ∪ ∂U → R by

η(x) = \{ \begin{matrix}1 & if δ(o, x) ≤ k + 1; \\ \frac{3k − δ(o, x)}{2k − 1} & if k + 1 < δ(o, x) < 3k; \\ 0 & if δ(o, x) ≥ 3k. \end{matrix}

Then |η(x) − η(y)| ≤ k^{−1} if x ∼ y. Now the Poincaré inequality (1.7) and Corollary 2.12 imply that

\frac{1}{|B|} ∑_{x∈B} |v(x) − v_{B}| ≤ (\frac{1}{|B|} ∑_{x∈B} |v(x) − v_{B}|^{p})^{1/p}

≤ ck(\frac{1}{|B|} ∑_{x∈B} |∇_{p} log u(x)|^{p})^{1/p}

≤ ck|B|^{−1/p}( ∑_{x⃗y∈E(3B)} |η(y) − η(x)|^{p})^{1/p}

≤ c|B|^{−1/p}(card E(3B))^{1/p} ≤ c.

This proves the lemma.

In particular, it follows from 3.10 and 3.12 that

(3.13)  (\frac{1}{|B|} ∑_{B} u^{Q})^{1/Q} ≤ 9(\frac{1}{|B|} ∑_{B} u^{−Q})^{−1/Q}

if 3B ⊂ U and u is positive and p-harmonic in U; see e.g. [HKM, p. 71]. Furthermore, the constant Q depends only on p and on the constants in (D) and in (P_{p}).

It is worth pointing out that one can prove Corollary 2.12 and hence Lemma 3.12 directly for positive p-superharmonic functions, too.

We are now ready to prove the Harnack inequality.

Proof of 1.8. Suppose that B = B(o, 2^{N}) is a ball and that u is a positive p-harmonic function in 6B. We shall prove an inequality

(3.14)  max_{x∈B} u(x) ≤ C_{1} min_{x∈B} u(x),

where the constant C_{1} is independent of u and B. If N ≤ 10, say, we obtain (3.14) with a constant C′_{1} = C′_{1}(p, d) by iterating the local Harnack inequality (2.4). Suppose that N > 10. For each i = 0, 1, …, N − 2, set r_{i} = 2^{N} + 2^{N−i} and B_{i} = B(o, r_{i}). Furthermore, define η_{i}: V → R by

η_{i}(x) = \{ \begin{matrix}1 & if δ(o, x) ≤ r_{i+1} + 1; \\ \frac{r_{i} − δ(o, x)}{r_{i} − r_{i+1} − 1} & if r_{i+1} + 1 < δ(o, x) < r_{i}; \\ 0 & if δ(o, x) ≥ r_{i}. \end{matrix}

Then |η_{i}(x)−η_{i}(y)| ≤ (r_{i} −r_{i+1} −1)^{−1} ≤ 2(r_{i} −r_{i+1})^{−1} if x ∼ y. Let λ and Q be the constants in the Sobolev inequality (1.6) and in Corollary 3.10, respectively. First we observe that there is q_{0} ∈ [Q/λ, Q] such that

(3.15)  |q_{0}λ^{i} − p + 1| ≥ \frac{(p − 1)(λ − 1)}{λ + 1}

for every i. Later another choice for q_{0} will be q_{0} = −Q which, as well as any negative number, satisfies (3.15) for all i. Set q_{i} = q_{0}λ^{i} and κ_{i} = q_{i} − p + 1. By the doubling condition (D) and the Sobolev inequality (1.6)

(\frac{1}{|B_{i+1}|} ∑_{B_{i+1}} u^{q_{i}λ})^{1/λ} ≤ c(\frac{1}{|B_{i}|} ∑_{B_{i}} |η_{i}u^{q_{i}/p}|^{λp})^{1/λ} ≤ \frac{cr_{i}^{p}}{|B_{i}|} ∑_{B_{i}} |∇_{p}(η_{i}u^{q_{i}/p})|^{p}.

To estimate the right hand side, we first observe that

∑_{B_{i}}|∇_{p}(η_{i}u^{q_{i}/p})|^{p} = 2 ∑_{x⃗y∈E(B_{i})} |η_{i}(y)u^{q_{i}/p}(y) − η_{i}(x)u^{q_{i}/p}(x)|^{p}

= 2 ∑_{x⃗y∈E(B_{i})}|η_{i}(x)(u^{q_{i}/p}(y) − u^{q_{i}/p}(x)) + u^{q_{i}/p}(y)(η_{i}(y) − η_{i}(x))|^{p}

≤ c ∑_{x⃗y∈E(B_{i})}(η_{i}^{p}(x) + η_{i}^{p}(y))|u^{q_{i}/p}(y) − u^{q_{i}/p}(x)|^{p}

+ c ∑_{x⃗y∈E(B_{i})}(u^{q_{i}}(y) + u^{q_{i}}(x))|η_{i}(y) − η_{i}(x)|^{p}.

Next we estimate

|u^{q_{i}/p}(y) − u^{q_{i}/p}(x)| ≤ \frac{|q_{i}|}{p}(u^{q_{i}/p−1}(y) + u^{q_{i}/p−1}(x))|u(y) − u(x)|.

Using this and the Caccioppoli inequality (2.2) we get

∑_{x⃗y∈E(B_{i})}(η_{i}^{p}(x) + η_{i}^{p}(y))|u^{q_{i}/p}(y) − u^{q_{i}/p}(x)|^{p}

≤ c|q_{i}|^{p} ∑_{x⃗y∈E(B_{i})}(η_{i}^{p}(x) + η_{i}^{p}(y))(u^{q_{i}−p}(y) + u^{q_{i}−p}(x))|u(y) − u(x)|^{p}

≤ c(|q_{i}|c_{2}(κ_{i}))^{p} ∑_{x⃗y∈E(B_{i})}(u^{q_{i}}(x) + u^{q_{i}}(y))|η_{i}(y) − η_{i}(x)|^{p},

where c_{2}(κ_{i}) = c max{1/|κ_{i}|, 1}. Hence

\begin{aligned}(\frac{1}{|B_{i+1}|} ∑_{B_{i+1}} u^{q_{i}λ})^{1/λ} & ≤ \frac{cr_{i}^{p} \{[|q_{i}|c_{2}(κ_{i})]^{p} + 1\}}{|B_{i}|}× \\ & × ∑_{x⃗y∈E(B_{i})}(u^{q_{i}}(x) + u^{q_{i}}(y))|η_{i}(y) − η_{i}(x)|^{p}. \end{aligned}

For any x ∼ y, r_{i}^{p}|η_{i}(y) − η_{i}(x)|^{p} ≤ cr_{i}^{p}(r_{i} − r_{i+1})^{−p} ≤ c2^{ip} and η_{i}(y) = η_{i}(x) = 0 if at least one of the points x or y belongs to ∂B_{i}. Therefore we get

(\frac{1}{|B_{i+1}|} ∑_{B_{i+1}} u^{q_{i}λ})^{1/λ} ≤ \frac{c2^{ip} \{[|q_{i}|c_{2}(κ_{i})]^{p} + 1\}}{|B_{i}|} ∑_{B_{i}} u^{q_{i}}.

By iteration we obtain

(3.16) (\frac{1}{|B_{j}|} ∑_{B_{j}} u^{q_{0}λ^{j}})^{1/λ^{j}} ≤ c^{S_{j}}2^{pS′_{j}} ∏_{i=0}^{j−1} \{[|q_{0}λ^{i}|c_{2}(κ_{i})]^{p} + 1\}^{1/λ^{i}} \frac{1}{|B_{0}|} ∑_{B_{0}} u^{q_{0}},

where j = N − 2, S_{j} = ∑_{i=0}^{j} λ^{−i}, and S′_{j} = ∑_{i=0}^{j} iλ^{−i}. The crucial point is that

(3.17)  c^{S_{j}}2^{pS′_{j}} ∏_{i=0}^{j−1} {[|q_{0}λ^{i}|c_{2}(κ_{i})]^{p} + 1}^{1/λ^{i}} ≤ C_{2},

with C_{2} independent of N, since q_{0} ∈ [Q/λ, Q] satisfies (3.15) for every i. Thus by (3.16), (3.17), and by Hölder’s inequality

(\frac{1}{|B_{j}|} ∑_{B_{j}} u^{Qλ^{j−1}})^{1/(Qλ^{j−1})} ≤ C_{2}^{1/q_{0}}(\frac{1}{|B_{0}|} ∑_{B_{0}} u^{Q})^{1/Q}.

On the other hand, (3.15) and (3.17) hold also for q_{0} = −Q, and so

(\frac{1}{|B_{j}|} ∑_{B_{j}} u^{−Qλ^{j}})^{−1/(Qλ^{j})} ≥ C_{2}^{−1/Q}(\frac{1}{|B_{0}|} ∑_{B_{0}} u^{−Q})^{−1/Q}.

Since 3B_{0} = 6B, we have

(\frac{1}{|B_{0}|} ∑_{B_{0}} u^{Q})^{1/Q} ≤ 9(\frac{1}{|B_{0}|} ∑_{B_{0}} u^{−Q})^{−1/Q}

by (3.13). Putting the last three estimates together we obtain

(\frac{1}{|B_{j}|} ∑_{B_{j}} u^{Qλ^{j−1}})^{1/(Qλ^{j−1})} ≤ c(\frac{1}{|B_{j}|} ∑_{B_{j}} u^{−Qλ^{j}})^{−1/(Qλ^{j})}.

Now

(\frac{1}{|B_{j}|} ∑_{B_{j}} u^{Qλ^{j−1}})^{1/(Qλ^{j−1})} ≥ |B_{j}|^{−1/(Qλ^{j−1})} max_{B_{j}} u

and

(\frac{1}{|B_{j}|} ∑_{B_{j}} u^{−Qλ^{j}})^{−1/(Qλ^{j})} ≤ |B_{j}|^{1/(Qλ^{j})} min_{B_{j}} u,

and so

max_{B_{j}} u ≤ c|B_{j}|^{(λ+1)/(Qλ^{j})} min_{B_{j}} u.

Since j = N − 2, |B_{j}| ≤ |B(o, 2^{N+1})| ≤ c^{N}. Therefore

|B_{j}|^{(λ+1)/(Qλ^{j})} ≤ c^{N(λ+1)/(Qλ^{N−2})} ≤ c,

with c independent of N. This proves the Harnack inequality for N > 10 since now

max_{B} u ≤ max_{B_{j}} u ≤ C′′_{1} min_{B_{j}} u ≤ C′′_{1} min_{B} u.

To complete the proof, take C_{1} = max{C′_{1}, C′′_{1}}.

4. Examples and the sharpness of the assumptions

Examples. Here we give some examples of graphs that satisfy (D) and (P_{p}). Recall from [K1] that a map f: X → Y between metric spaces (X, d) and (Y, d) is called a rough isometry if there are constants a, b, c ≥ 0 such that the c-neighborhood of fX coincides with Y and that

a^{−1}d(x, y) − b ≤ d(f(x), f(y)) ≤ ad(x, y) + b

holds for all x, y ∈ X. In [CS2] Coulhon and Saloff-Coste obtained several useful results concerning the invariance of Poincaré and Sobolev inequalities under rough isometries. For instance, if a graph Γ_{1} of bounded degree is roughly isometric to another graph Γ_{2} which satisfies the conditions (D) and (P_{1} ), then the same conditions hold also on Γ_{1} . The above remains true if we replace Γ_{2} by a Riemannian manifold of bounded geometry which satisfies the obvious versions of (D) and (P_{1} ). For instance, any complete Riemannian manifold whose Ricci curvature is nonnegative satisfies (D) and (P_{1} ) by the Bishop–Gromov comparison principle and by Buser’s isoperimetric inequality; see [CGT], and [Bu], respectively. In particular, the n-dimensional grid Γ^{n} = (Z^{n}, E), and also every graph of bounded degree that is roughly isometric to R^{n}, n ≥ 1, is p-strong Liouville for any p > 1. Above E is the natural edge set, i.e., there is an edge between vertices x, y ∈ Z^{n} if and only if |x − y| = 1. Furthermore, Cayley graphs of discrete finitely generated groups of polynomial growth satisfy (D) and (P_{1} ), and so they are p-strong Liouville for every p > 1. The fact that such Cayley graphs satisfy (P_{1} ) seems to be well-known (see e.g. [CS1], [CS2] and [SC1]), the proof being the same as the one for Lie groups of polynomial growth; see [V2] and [SC2].

It is also possible to obtain Poincaré inequalities from isoperimetric inequalities. Let Γ = (V, E) be a graph of bounded degree and let B ⊂ V be a ball. Suppose that there exist constants n > 1 and c > 0 such that

(4.1)  |D|^{(n−1)/n} ≤ c|∂D ∩ B|

whenever B ⊂ V is a ball and D ⊂ B, with |D| ≤ |B|/2. We claim that the isoperimetric inequality (4.1) is equivalent to a Poincaré-type inequality

(4.2)  inf_{a∈R}(∑_{x∈B} |u(x) − a|^{n/(n−1)})^{(n−1)/n} ≤ c ∑_{x∈B} |∇_{1}u(x)|,

where u is a function in B ∪ ∂B. To prove this claim, let u be a (nonconstant) function in B ∪ ∂B. First we choose a value a = u(x_{ν}), x_{ν} ∈ B, such that the sets B_{+} = {x ∈ B : u(x) > a} and B_{−} = {x ∈ B : u(x) < a} satisfy |B_{±}| ≤ |B|/2. Such a vertex x_{ν} can be found, for instance, by labeling all the vertices of B by x_{1}, x_{2}, …, x_{k} such that u(x_{1}) ≤ u(x_{2}) ≤ ⋯ ≤ u(x_{k}) and then setting ν = [k/2] + 1, where [k/2] is the integer part of k/2. If B_{+} ≠ ∅, we let 0 = β_{0} < β_{1} < ⋯ < β_{N} be all non-negative values that u − a takes in B. Furthermore, let K_{i} = {x ∈ B : u(x) − a ≥ β_{i}}. Then an argument similar to that in [MMT, p. 14] (see also [CF, p. 483–484]) yields

∑_{x∈B_{+}}(u(x) − a)^{n/(n−1)} = ∑_{i=1}^{N}(β_{i}^{n/(n−1)} − β_{i−1}^{n/(n−1)})|K_{i}|

≤ (∑_{i=1}^{N}(β_{i} − β_{i−1})|K_{i}|^{(n−1)/n})^{n/(n−1)}

≤ c(∑_{i=1}^{N}(β_{i} − β_{i−1})|∂K_{i} ∩ B|)^{n/(n−1)}

≤ c(∑_{x∈B} |∇_{1}u(x)|)^{n/(n−1)}.

Similarly we obtain

∑_{x∈B_{−}}(a − u(x))^{n/(n−1)} ≤ c(∑_{x∈B} |∇_{1}u(x)|)^{n/(n−1)}.

Hence (4.2) holds. Conversely, if (4.2) holds, the isoperimetric inequality (4.1) follows by applying (4.2) to the characteristic function of D. For example, Γ^{n} satisfies the Poincaré inequality (4.2) since (4.1) is inherited from the corresponding isoperimetric inequality in R^{n}. So we reinvent the fact that Γ^{n} is p-strong Liouville for every p > 1. Observe that in this case, the Sobolev–Poincaré inequality (1.5) follows directly from (4.2) without using Lemma 1.4.

The sharpness of the assumptions. We finish the paper by discussing what may happen if we omit one of the conditions (D) and (P_{p}). More precisely, we construct examples to show that, in general, both conditions (D) and (P_{p}) for Γ are needed to ensure that Γ is p-strong Liouville.

It is easy to see that the doubling condition alone is not sufficient to obtain strong Liouville. Indeed, take two copies of Z^{n}, n ≥ 2, and join them together by an edge. Let o be an endpoint of the joining edge. Then the resulting graph Γ_{1} still satisfies the doubling condition (D) but every weak (1, p)-Poincaré inequality fails to hold if p < n. The latter can be seen by assuming that a weak (1, p)- Poincaré inequality exists on Γ_{1} and then applying it to a ball B(o, r) and to a function which is identically 0 in one copy of Z^{n} and identically 1 in the other copy of Z^{n}. What we then get is roughly an inequality 1 ≤ cr^{1−n/p} which leads to a contradiction if r → ∞ and p < n. On the other hand, using ideas from [H3] it is possible to construct nonconstant positive (or even bounded) p-harmonic functions on Γ for every 1 < p < n.

It is harder to construct a graph which satisfies a weak (1, p)-Poincarè inequality but which is not p-strong Liouville. Anyway, here is an example. Construct a graph Γ_{2} whose vertex set X is a disjoint union of Z and Z^{2} . The edge set consists of the (standard) edges in Z and in Z^{2} and of one edge joining the vertices o_{1} := 0 ∈ Z and o_{2} := (0, 0) ∈ Z^{2} . Now the doubling condition fails which we see by choosing, for every integer k > 0, a point y ∈ Z whose distance from o_{1} is k. Then |B(y, k)| ≈ k but |B(y, 2k)| ≈ k^{2} . On the other hand, Γ_{2} has nonconstant positive p-harmonic functions for 1 < p < 2. These can be constructed again by using the methods of [H3]. Finally, we show that the (1, 1)-Poincaré inequality holds on Γ_{2} . To do this, let B = B(x, k) ⊂ X be an arbitrary ball. If B lies entirely either in Z or in Z^{2} , there is nothing to prove since both Z and Z^{2} have (1, 1)-Poincaré inequalities. So we are left with the case where B is a disjoint union of balls B^{1} ⊂ Z and B^{2} ⊂ Z^{2} . For instance, if x ∈ Z^{2} , then B^{2} = B^{2}(x, k) ⊂ Z^{2} and B^{1} = B^{1}(o_{1}, k − δ(x, o_{2}) − 1) ⊂ Z. Let u be a function in 2B ∪ ∂(2B). Then

\begin{aligned}|B| ∑_{y∈B} |u(y) − u_{B}| & = |B| ∑_{y∈B}|u(y) − |B|^{−1} ∑_{z∈B} u(z)| \\ & = ∑_{y∈B}|∑_{z∈B}(u(y) − u(z))| ≤ S_{1} + S_{2} + S_{3}. \end{aligned}

The terms S_{i} will be specified and estimated below. For i = 1, 2,

\begin{aligned}S_{i} & := ∑_{y∈B^{i}}| ∑_{z∈B^{i}}(u(y) − u(z))| = |B^{i}| ∑_{y∈B^{i}} |u(y) − u_{B^{i}}| \\ & ≤ c|B^{i}|k ∑_{y∈B^{i}} |∇_{1}u(y)|, \end{aligned}

where in the last step we made use of the Poincaré inequalities in Z and in Z^{2} , respectively. To estimate S_{3} , we use some ideas from [DS] and [CS1]. More precisely,

\begin{aligned}S_{3} & := ∑_{y∈B^{1}}| ∑_{z∈B^{2}}(u(y) − u(z))| + ∑_{y∈B^{2}}| ∑_{z∈B^{1}}(u(y) − u(z))| \\ & ≤ 2 ∑_{(y,z)∈B^{1}×B^{2}} |u(y) − u(z)| ≤ 2 ∑_{(y,z)∈B^{1}×B^{2}} ∑_{e∈γ_{y,z}} |u(e_{+}) − u(e_{−})|. \end{aligned}

Here and from now on γ_{y,z} is a chain from y to z of (oriented) edges e, whose endpoints e_{−} and e_{+} belong to B. We want to estimate the right hand side of the final inequality in terms of ∑_{y∈B} |∇_{1}u(y)|. To do this effectively, we must be able to choose, for every pair (y, z) ∈ B^{1} × B^{2} , a chain γ_{y,z} such that no edge e will belong to too many γ_{y,z} ’s. Observe that each γ_{y,z} contains the edge o⃗_{1}o_{2} . On the other hand, one can show by induction that it is possible to join o_{2} to z ∈ B^{2} by a chain such that after the joining is done for every z ∈ B^{2} , each edge e will be traversed at most 4(diam B^{2})^{2} times. Hence we may choose the chains γ_{y,z}, (y, z) ∈ B^{1} × B^{2} , so that each edge e belongs to at most 8(diam B^{1})(diam B^{2})^{2} chains. We obtain

S_{3} ≤ c(diam B^{1})(diam B^{2})^{2} ∑_{y∈B} |∇_{1}u(y)|,

with c independent of B. Finally, we observe that |B|^{−1}(diam B^{1})(diam B^{2})^{2} ≤ ck. Putting the estimates for S_{i} together we get that

∑_{y∈B} |u(y) − u_{B}| ≤ |B|^{−1}(S_{1} + S_{2} + S_{3}) ≤ ck ∑_{y∈B} |∇_{1}u(y)|,

where c is independent of k. Thus the (1, 1)-Poincaré inequality holds on Γ_{2} .

References

[A] Ancona, A.: Théorie du potentiel sur les graphes et les variétés. - In: École d’été de probabilités de Saint-Flour XVIII–1988, Lecture Notes in Math. 1427, Springer-Verlag, Berlin, 1990, 5–112.

[B] Benjamini, I.: Instability of the Liouville property for quasi-isometric graphs and manifolds of polynomial volume growth. - J. Theoret. Probab. 4, 1991, 631–637.

[BS] Benjamini, I., and O. Schramm: Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. - Preprint.

[Bu] Buser, P.: A note on the isoperimetric constant. - Ann. Sci. École Norm. Sup. 15, 1982, 213–230.

[CF] Chavel, I., and E.A. Feldman: Modified isoperimetric constants, and large time heat diffusion in Riemannian manifolds. - Duke Math. J. 64, 1991, 473–499.

[CGT] Cheeger, J., M. Gromov, and M. Taylor: Finite propagation speed, kernel estimates for functions of the Laplace operator, and the geometry of complete Riemannian manifolds. - J. Differential Geometry 17, 1982, 15–53.

[CW1] Coifman, R., and G. Weiss: Analyse harmonique non-commutative sur certains espaces homogenes. - Lecture Notes in Math. 242, Springer-Verlag, Berlin–Heidelberg–New York, 1971.

[CW2] Coifman, R., and G. Weiss: Extensions of Hardy spaces and their use in analysis. - Bull. Amer. Math. Soc. 83, 1977 , 569–645.

[CS1] Coulhon, T., and L. Saloff-Coste: Isopérimétrie pour les groupes et les variétés. - Rev. Mat. Iberoamericana 9, 1993, 293–314.

[CS2] Coulhon, T., and L. Saloff-Coste: Variétés riemanniennes isométriques á l’infini. - Rev. Mat. Iberoamericana 11, 1995, 687–726.

[De] Delmotte, T.: Inégalité de Harnack elliptique sur les graphes. - Preprint.

[DS] Diaconis, P., and D. Stroock: Geometric bounds for eigenvalues of Markov chains. - Ann. Appl. Probab. 1, 1991, 39–61.

[FS] Folland, G.B., and E.M. Stein: Hardy Spaces on Homogeneous Groups. - Princeton University Press, Princeton, New Jersey, 1982.

[HK] Hajłasz, P., and P. Koskela: Sobolev meets Poincaré. - C. R. Acad. Sci. Paris Sér I Math. 320, 1995, 1211–1215.

[HKM] Heinonen, J., T. Kilpeläinen, and O. Martio: Nonlinear Potential Theory of Degenerate Elliptic Equations. - Oxford Mathematical Monographs, Clarendon Press, Oxford–New York–Tokyo, 1993.

[HeK] Heinonen, J., and P. Koskela: Quasiconformal maps in metric spaces with controlled geometry. - Preprint.

[H1] Holopainen, I.: Positive solutions of quasilinear elliptic equations on Riemannian manifolds. - Proc. London Math. Soc. (3) 65, 1992, 651–672.

[H2] Holopainen, I.: Rough isometries and p-harmonic functions with finite Dirichlet integral. - Rev. Mat. Iberoamericana 10, 1994, 143–176.

[H3] Holopainen, I.: Solutions of elliptic equations on manifolds with roughly Euclidean ends. - Math. Z. 217, 1994, 459–477.

[HS] Holopainen, I., and P.M. Soardi: p-harmonic functions on graphs and manifolds. - Preprint.

[JN] John, F., and L. Nirenberg: On functions of bounded mean oscillation. - Comm. Pure Appl. Math. 14, 1961, 415–426.

[K1] Kanai, M.: Rough isometries and combinatorial approximations of geometries of noncompact Riemannian manifolds. - J. Math. Soc. Japan 37, 1985, 391–413.

[K2] Kanai, M.: Rough isometries and the parabolicity of Riemannian manifolds. - J. Math. Soc. Japan 38, 1986, 227–238.

[L] Lyons, T.: Instability of the Liouville property for quasi-isometric Riemannian manifolds and reversible Markov chains. - J. Differential Geometry 26, 1987, 33–66.

[LS] Lyons, T., and D. Sullivan: Function theory, random paths and covering spaces. - J. Differential Geometry 19, 1984, 299–323.

[MMT] Markvorsen, S., S. McGuinness, and C. Thomassen: Transient random walks on graphs and metric spaces with applications to hyperbolic surfaces. - Proc. London Math. Soc. 64, 1992, 1–20.

[RSV] Rigoli, M., M. Salvatori, and M. Vignati: Subharmonic functions on graphs. - Preprint.

226 Ilkka Holopainen and Paolo M. Soardi

[SC1] Saloff-Coste, L.: On global Sobolev inequalities. - Forum Math. 6, 1994, 271–286.

[SC2] Saloff-Coste, L.: Parabolic Harnack inequality for divergence form second order differential operators. - Potential Analysis 4, 1995, 429–467.

[SC3] Saloff-Coste, L.: Inequalities for p-superharmonic functions on networks. - Preprint.

[S1] Soardi, P.M.: Rough isometries and Dirichlet finite harmonic functions on graphs. - Proc. Amer. Math. Soc. 119, 1993, 1239–1248.

[S2] Soardi, P.M.: Potential Theory on Infinite Networks. - Lecture Notes in Math. 1590, Springer-Verlag, Berlin–Heidelberg–New York, 1994.

[V1] Varopoulos, N.: Brownian motion and random walks on manifolds. - Ann. Inst. Fourier (Grenoble) 34, 1984, 243–269.

[V2] Varopoulos, N.: Fonctions harmoniques sur les groupes de Lie. - C. R. Acad. Sci. Paris Sér. I Math. 309, 1987, 519–521.

Received 22 November 1995