Logarithmic Harnack inequalities^{∗}

F. R. K. Chung University of Pennsylvania Philadelphia, Pennsylvania 19104^{†}

S.-T. Yau Harvard University Cambridge, Massachusetts 02138 ^{†}

1 Introduction

We consider the relationship between eigenvalues and the log-Sobolev constant for the Laplace operator on smooth compact Riemannian manifolds and for finite graphs. We will establish Logarithmic Harnack inequalities which can be used to derive lower bounds for log-Sobolev constants.

Logarithmic Sobolev inequalities first arose in the analysis of elliptic differential operators in infinite dimensions. Many developments and applications can be found in several survey papers [1, 9, 12]. Recently, Diaconis and Saloff-Coste [8] considered logarithmic Sobolev inequalities for Markov chains. The lower bounds for log-Sobolev constants can be used to improve convergence bounds for random walks on graphs [5, 8]. The problem of bounding log-Sobolev constants tends to be harder than estimating eigenvalues. Logarithmic Harnack inequalities provide a direct approach for estimating the log-Sobolev constant. We will derive lower bounds for log-Sobolev constants for Riemannian manifolds and for large classes of graphs.

The continuous and discrete cases have a very similar flavor but they also have their natural differences. In this section, we will describe a unified approach and leave the detailed descriptions and definitions in Sections 2 and 3. We will give self-contained proofs for both manifolds and graphs.

For a smooth, compact, connected Riemannian manifold M, we let ∇ denote the gradient with the associated Laplace-Beltrami operator Δ. The logarithmic Sobolev inequality is of the following form:

∫_{M} |∇f(x)|^{2} ≥ α ∫_{M} f^{2}(x) log f^{2}(x)  (1)

for a function f : M → ℝ satisfying ∫ |f|^{2} = vol M. The log-Sobolev constant is the largest α

satisfying (1) for any function f defined on M.

We will show that the function f on M achieving the log-Sobolev constant α satisfies the following logarithmic Harnack inequality:

|∇f|^{2} + αf^{2} log f^{2} ≤ α sup(f^{2} log f^{2})  (2)

∗To appear in Mathematics Research Letters

†Research supported in part by NSF Grant No. DMS 95-04834

provided that M has non-negative Ricci curvature. The inequality in (2) is similar to the Harnack inequality except for a logarithmic factor. It can be used to derive the following lower bound for log-Sobolev constants for d-dimensional compact Riemannian manifold M (A similar inequality was proved by Deuschel and Stroock [7] by a different method):

α ≥ min\{\frac{λ_{1}}{8e} , \frac{1}{d D^{2}(M)}\}  (3)

where D(M) denotes the diameter of M and λ_{1} is the first eigenvalue of the Laplacian.

For a graph G = (V, E) with Laplacian L, the log-Sobolev constant α can be expressed as follows:

α = inf_{f≠0} \frac{∑_{\{x,y\}∈E}(f(x) − f(y))^{2}}{∑_{x∈V} f^{2}(x)d_{x} log f^{2}(x)}  (4)

where f ranges over all nontrivial functions f : V → ℝ satisfying ∑_{x} f^{2}(x)d_{x} = vol G and d_{x}

denotes the degree of x. The function f achieving the log-Sobolev constant α satisfies:

∑_{y∼x}(f(x) − f(y)) = αd_{x}f(x) log f^{2}(x)  (5)

where y ranges over all y adjacent to x, denoted by y ∼ x.

For the discrete case, we can only establish the logarithmic Harnack inequality for Ricci flat graphs (which are defined later in Section 3).

∑_{y∼x}(f(x) − f(y))^{2} ≤ 6αd_{x} sup_{z} f^{2}(z) log f^{2}(z)(1 + \frac{α}{4} log f^{2}(z)).  (6)

For a graph G with isoperimetric dimension δ and isoperimetric constant c_{δ} (see the definition in Section 5) and with the assumption that G is a k-regular Ricci flat graph, we can use (6) to show that

α ≥ min\{\frac{c}{kD^{2}δ log δ} , \frac{c′}{k( vol G)^{2/δ}} \}  (7)

where D denotes the diameter of G, c denotes an absolute constant, and c′ depends on the isoperimetric constant.

The above results on logarithmic Harnack inequalities and can be extended to manifolds with convex boundary and for strongly convex graphs with Neumann and Dirichlet boundary conditions. This will be described in Section 6.

Since a random walk on a graph G on n vertices approaches stationarity after order log log n/α steps, the above lower bounds for the log-Sobolev constant α immediately implies a convergence bound of order (log log n)kD^{2} if the isoperimetric dimension is bounded.

2 On a compact Riemannian manifold

Let M be a smooth connected compact Riemannian manifold and Δ be a Laplace operator associated with the Riemannian metric, i.e., in coordinates x_{1}, x_{2}, ...x_{n}

Δ = \frac{1}{\sqrt{g}} ∑_{i,j=1}^{n} \frac{∂}{∂x_{i}}(\sqrt{g}g^{ij} \frac{∂u}{∂x_{j}} )

where g^{ij} are contra-variant components of the metric tensor, g = det ∥g_{ij}∥ and u is a smooth function on M. The Laplace operator with the boundary condition is self-adjoint and has a discrete spectrum in L^{2}(M, μ), where μ is the Riemannian measure;

If the manifold M has a boundary ∂M, we consider either Dirichlet or Neumann boundary conditions. The boundary condition implies u\frac{∂u}{∂ν} ≤ 0 where ν is the outer normal field on ∂M.

We also consider a distance function dist(x, y) on M × M which may be equal to the geodesic distance, but in general does not have to be. Other than being a distance function, the function dist(x, y) must be Lipschitz and, moreover, for all x, y ∈ M, |∇dist(x, y)| ≤ 1. Suppose f satisfies

∫_{M} |f|^{2} = vol M and f achieves the log-Sobolev constant. That is,

α = \frac{∫_{M} |∇f|^{2}}{∫_{M} f^{2} log f^{2}} = inf_{g≠0} \frac{∫_{M} |∇g|^{2}}{∫_{M} g^{2} log g^{2}} .

We may assume that the function f achieving α is non-negative (since we can use |f| and the ratio above is not increased.)

By Lagrange’s method, we have

\frac{−2Δf}{∫_{M} f^{2} log f^{2}} − \frac{2(f log f^{2} + 2f) ∫_{M} |Δf|^{2}}{(∫_{M} f^{2} log f^{2})^{2}} + c_{1}f = 0  (8)

for some constant c_{1}. After substituting for α and simplifying, we get

− Δf − α(f log f^{2} + 2f) + c_{2}f = 0.  (9)

After multiplying (9) by f and integrating over M, we have

∫_{M} |∇f|^{2} − α ∫_{M} f^{2}(log f^{2} + 2) + c_{2} ∫_{M} f^{2} = 0.

This implies c_{2} = 2α. Therefore we obtain from (9) that Δf = −αf log f^{2} which was also proved in [10].

Theorem 1 If f achieves log-Sobolev constant α and ∫_{M} f^{2} = vol M, then f satisfies

Δf = −αf log f^{2}.  (10)

One of the consequences of (10) is f(x) ≠ 0 for all x. To see this, we note that f ∈ L^{p} for any

p > 1 since ∫ |∇f|^{2} < ∞ and ∫ f^{2} = volM. Hence, Δf ∈ L^{p} for any p > 1 and ∑ f_{ij}^{2} ∈ L^{p} for

any p > 0. By a standard bootstrap argument, one can then prove that f is smooth everywhere. If f(x) = 0 and vanishes only up to finite order at x, (10) shows that f cannot be smooth. On the other hand, if f vanishes up to infinite order at x, the unique continuity argument shows that f ≡ 0. Hence, we may assume f(x) > 0 for all x.

Theorem 2 Suppose M is a d-dimensional connected compact Riemannian manifold with nonnegative Ricci curvature.. If f > 0 solves (10), then we have

sup f ≤ e^{d/2}

and

|∇f|^{2} + 2αf^{2} log f ≤ αdf^{2}.

Proof: Let φ = log f. Then we have

Δφ = \frac{Δf}{f} − |∇ log f|^{2}
= −α log f^{2} − |∇φ|^{2}
= −2αφ − |∇φ|^{2}

by using Theorem 1. We consider ϕ = |∇φ|^{2} + 2αφ. Let x_{0} denote a maximum point of ϕ. Then the derivatives ϕ_{i} satisfy ϕ_{i}(x_{0}) = 0 and

ϕ_{i} = 2 ∑_{j} φ_{j}φ_{ji} + 2αφ_{i}.  (11)

Also,

Δϕ = 2 ∑ φ_{ij}^{2} + 2φ_{j}(Δφ)_{j} + 2 ∑ R_{ij}φ_{i}φ_{j} + 2αΔφ.

Using Theorem 1 and substituting for Δφ = −ϕ, we have

Δϕ = 2 ∑ φ_{ij}^{2} − 2 ∑ φ_{i}ϕ_{i} + 2 ∑ R_{ij}φ_{i}φ_{j} − 2αϕ
≥ \frac{2}{d}(Δφ)^{2} − 2 ∑ φ_{i}ϕ_{i} + 2 ∑ R_{ij}φ_{i}φ_{j} − 2αϕ
≥ \frac{2}{d}ϕ^{2} − 2 ∑ φ_{i}ϕ_{i} + 2 ∑ R_{ij}φ_{i}φ_{j} − 2αϕ.

Since 0 ≥ Δϕ(x_{0}) at a maximum point x_{0} and R_{ij} ≥ 0, we have ϕ(x_{0}) ≤ αd. This implies ϕ(x) ≤ ϕ(x_{0}) ≤ αd. Hence, we have

|∇φ|^{2} + 2αφ ≤ αd

which is equivalent to

|∇f|^{2} + 2αf^{2} log f ≤ α d f^{2}.

Suppose y_{0} is a maximum point of f. Then we have ∇f(y_{0}) = 0 and

U = sup_{y} f(y) ≤ e^{d/2}.

Theorems 1 and 2 will be repeatedly used for establishing the following logarithmic Harnack inequality:

Theorem 3 Suppose M is a compact Riemannian manifold with non-negative Ricci curvature and the function f solves (10). Then we have

|∇f|^{2} + αf^{2} log f^{2} ≤ α sup(f^{2} log f^{2}).

In particular, we have

|∇f|^{2} ≤ αU^{2} log U^{2} + α/e

where U = sup f ≥ 1 and e is the base of the natural logarithm.

Proof: We consider

F = |∇f|^{2} + αf^{2} log f^{2}

Let x_{0} denote a maximum point of F. Then the derivatives F_{i} satisfies F_{i}(x_{0}) = 0.

F_{i} = 2 ∑_{j} f_{j}f_{ji} + 2αf f_{i} log f^{2} + 2αf f_{i}.  (12)

ΔF = 2 ∑ f_{ij}^{2} + 2 ∑_{j} f_{j}(Δf)_{j} + 2 ∑ R_{ij}f_{i}f_{j} + 2α|∇f|^{2} log f^{2}
+4α|∇f|^{2} + 2αf Δf log f^{2} + 2α|Δf|^{2} + 2αf Δf.

Using Theorem 1 to substitute for Δf, we have

ΔF = 2 ∑ f_{ij}^{2} − 2α|∇f|^{2} log f^{2} − 4α|∇f|^{2} + 2 ∑ R_{ij}f_{i}f_{j}
+2α|∇f|^{2} log f^{2} + 4α|∇f|^{2} − 2α^{2}f^{2} log^{2} f^{2} + 2α|∇f|^{2} − 2α^{2}f^{2} log f^{2}.

After cancellations, we have

ΔF = 2 ∑_{ij} f_{ij}^{2} + 2 ∑ R_{ij}f_{i}f_{j} − 2α^{2}f^{2} log^{2} f^{2} + 2α|∇f|^{2} − 2α^{2}f^{2} log f^{2}.  (13)

We may choose a frame such that f_{i} = 0 for i > 1. Since F_{1}(x_{0}) = 0, we conclude from (12) that if f_{1} ≠ 0,

2f_{11} + 2αf log f^{2} + 2αf = 0.

This implies

f_{11}^{2} = α^{2}f^{2}(log^{2} f^{2} + 2 log f^{2} + 1).

Substituting into (13), we obtain

ΔF ≥ 2 ∑_{i,j≠1} f_{ij}^{2} + 2 ∑ R_{ij}f_{i}f_{j} + 2α^{2}f^{2} log f^{2} + 2α|Δf|^{2}

When R_{ij} ≥ 0, this inequality cannot hold at x_{0}. Hence ∇f = 0 at x_{0} and we conclude that

F (x) ≤ F (x_{0}) = α sup(f^{2} log f^{2}).

In particular, we have

|∇f|^{2} ≤ αU^{2} log U^{2} + α sup_{0<z≤1} z^{2} log z^{2} ≤ αU^{2} log U^{2} + α/e.

This completes the proof for Theorem 3. □

Theorem 4 The log-Sobolev constant α of a smooth connected compact manifold with non-negative Ricci curvature in d-dimensions satisfies

α ≥ min\{\frac{λ_{1}}{8e} , \frac{1}{d D^{2}(M)}\}

where D(M) denotes the diameter of M and λ_{1} is the first eigenvalue of the Laplacian.

Proof: Let f denote the function achieving α and ∫_{M} f^{2} = vol M. We consider two possibilities:

Case 1: sup |f − 1| ≤ β. We consider f = 1 + g. By Theorem 1, we have Δf = −αf log f^{2}. We consider

−gΔg = αg(1 + g) log(1 + g)^{2}.

This implies

∫_{M} |∇g|^{2} = α ∫_{M} g(1 + g) log(1 + g)^{2}
≤ 2(1 + β)α ∫_{M} |g| log(1 + |g|)
≤ 2(1 + β)α ∫_{M} g^{2}.  (14)

On the other hand, from the definition of eigenvalues we have

∫_{M} |∇g|^{2} ≥ λ(∫_{M} g^{2} − \frac{(∫_{M} g)^{2}}{vol M})

Since ∫_{M} f^{2} = ∫_{M}(1 + g)^{2} = vol M, and sup |g| ≤ β, we have

− ∫_{M} g = \frac{1}{2} ∫_{M} g^{2} ≤ \frac{β^{2}}{2} vol M.

This implies

∫_{M} |∇g|^{2} ≥ λ(∫_{M} g^{2} − \frac{(∫_{M} g)^{2}}{vol M}) ≥ λ(1 − \frac{β^{2}}{4} ) ∫_{M} g^{2}.

Together with (14), we have

α ≥ \frac{1}{2(1 + β)}(1 − \frac{β^{2}}{4} )λ_{1}.

Using known eigenvalue lower bounds on d-dimensional smooth compact Riemannian manifold, we have

α ≥ \frac{const.}{D^{2}(M)}.

Case 2: sup |f − 1| ≥ β. From Theorem 2, we have

|∇ log f|^{2} ≤ α(d − 2 log f).

There is a path γ so that f(γ(0)) = 1 and either f(γ(1)) = 1 − β or f(γ(1)) = 1 + β. In both cases, we can assume that the length of γ is no more than the diameter D(M) of M. In the former case, we have

− log(1 − β) ≤ ∫_{γ} |∇ log f|
−\sqrt{d} + \sqrt{d − 2 log(1 − β)} ≤ ∫_{γ} \frac{|∇ log f|}{\sqrt{d − 2 log f}} ≤ \sqrt{α}D(M).

In the latter case, we have

\sqrt{d} − \sqrt{d − 2 log(1 + β)} ≤ \sqrt{α}D(M).

Hence,

\sqrt{α}D(M) ≥ min (\frac{−2 log(1 − β)}{\sqrt{d} + \sqrt{d − 2 log(1 − β)}}, \frac{2 log(1 + β)}{\sqrt{d} + \sqrt{d − 2 log(1 + β)}}) .

If we choose β = 1, then in Case 1, we have α ≥ 3λ_{1}/16 and in case 2,

\sqrt{α}D(M) ≥ \frac{2 log 2}{\sqrt{d} + \sqrt{d − 2 log 2}} ≥ \frac{log 2}{\sqrt{d}}.

Note that we can choose any 0 < β < 2. In particular, β = e − 1 will give

α ≥ min (\frac{λ_{1}}{8e} , \frac{1}{dD(M)^{2}} ) .

□

We remark that we can consider log-Sobolev constants and logarithmic Harnack inequalities for manifolds with convex boundary. In fact, the proofs in Theorems 1-4 can be carried out in the same way for Laplace operators with Dirichlet and Neumann boundary conditions as long as the maximum points are interior points of the manifolds. This is indeed the case when we have convex boundary (or even weaker conditions). We also remark that the factor of d in Theorem 4 is necessary as shown by examples such as d-dimensional balls (see [12]).

3 Log-Sobolev constants for graphs

Let G denote a graph with vertex set V and edge set E. For a function f : V (G) → ℝ, we define

Lf(x) = ∑_{y∼x}(f(x) − f(y)).  (15)

It is easy to see that

⟨f, Lf⟩ = ∑_{x∼y}(f(x) − f(y))^{2}  (16)

where ∑_{x∼y} denotes the sum over all (unordered) adjacent pairs. Here ⟨f, g⟩ = ∑_{x} f(x)g(x) denotes the standard inner product in ℝ^{n}.

For a graph G, the log-Sobolev constant α of G is defined as:

α = inf_{f≠0} \frac{∑_{x∼y}(f(x) − f(y))^{2}}{∑_{x} f^{2}(x)d_{x} log f^{2}(x)}  (17)

where the infimum ranges over all nonzero functions g satisfying

∑_{x} g^{2}(x)d_{x} = ∑_{x} d_{x} = vol G

and d_{x} denotes the degree of x in G.

Theorem 5 For a graph G, suppose f : V → ℝ achieves the log-Sobolev constant and ∑_{x} f^{2}(x)d_{x} = vol G. Then f satisfies, for any vertex x,

Lf(x) = αf(x)d_{x} log f^{2}(x).

Proof: The proof is basically the same as in Theorem 1. We also use Lagrange’s method, by taking the derivative with respect to f(x):

\frac{2Lf(x)}{∑_{x} f^{2}(x) log f^{2}(x)} − \frac{2(f(x)d_{x} log f^{2}(x) + 2f(x)d_{x}) ∑_{x∼y}(f(x) − f(y))^{2}}{(∑_{x} f^{2}(x)d_{x} log f^{2}(x))^{2}} + c_{1}f(x) = 0

(18)

for some constant c_{1}. After substituting for α, the above expression can be simplified:

Lf(x) − α(f(x) log f^{2}(x) + 2f(x)) + c_{2}f(x) = 0.  (19)

After multiplying (19) by f(x) and summing over all x in V, we have

∑_{x∼y}(f(x) − f(y))^{2} − α ∑_{x} f^{2}(x)(log f^{2}(x) + 2) + c_{2} ∑_{x} f^{2}(x) = 0.

This implies c_{2} = 2α. Therefore we obtain from (19) that Lf(x) = αf(x)d_{x} log f^{2}(x).

4 Logarithmic Harnack inequalities for graphs

Let G = (V, E) denote a graph with vertex set V = V (G) and edge set E = E(G). For a vertex v, the neighborhood N(v) of v consists of v and vertices adjacent to v. We say G has a local k-frame at v if there are mappings η_{1}, ⋯, η_{k}: N(v) → V satisfying

(1) G is k-regular;

(2) u is adjacent to η_{i}u for every u ∈ V and 1 ≤ i ≤ k;

(3) η_{i}u ≠ η_{j}u if i ≠ j.

A graph G is said to be Ricci flat if G has a local k-frame and

⋃_{j} η_{i}η_{j}v = ⋃_{j} η_{j}η_{i}v

for any i and v.

For example, a homogeneous graph associated with an abelian group is Ricci flat [6].

We will prove the following logarithmic Harnack inequality for Ricci flat graphs.

Theorem 6 In a Ricci flat G, suppose a function f : V (G) → ℝ satisfies

Lf(x) = ∑_{y∼x}[f(x) − f(y)] = αkf(x) log f^{2}(x).

Then the following inequality holds for x ∈ V (G), and for U = sup_{y} |f(y)| ≥ 1:

∑_{y∼x}[f(x) − f(y)]^{2} ≤ 6kα max\{U^{2} log U^{2}(1 + \frac{α}{4} log^{2} U^{2}), 1\}.

Proof: We define ρ(x) = ∑_{y∼x}[f(x) − f(y)]^{2} and we consider

Lρ(x) = ∑_{i} ∑_{j}{[f(x) − f(η_{j}x)]^{2} − [f(η_{i}x) − f(η_{j}η_{i}x)]^{2}}
= − ∑_{i} ∑_{j}[f(x) − f(η_{j}x) − f(η_{i}x) + f(η_{j}η_{i}x)]^{2}

+2 ∑_{i} ∑_{j}[f(x) − f(η_{j}x) − f(η_{i}x) + f(η_{j}η_{i}x)][f(x) − f(η_{j}x)]

Let X denote the second term above. Then we have

X = 2 ∑_{i} ∑_{j}[f(x) − f(η_{j}x) − f(η_{i}x) + f(η_{j}η_{i}x)] [f(x) − f(η_{j}x)]
= 2 ∑_{j}{∑_{i}[f(x) − f(η_{j}x) − f(η_{i}x) + f(η_{i}η_{j}x)]}[f(x) − f(η_{j}x)]

+2 ∑_{j}[∑_{i}(f(η_{j}η_{i}x) − f(η_{i}η_{j}x))][f(x) − f(η_{j}x)]

= 2αk ∑_{j}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x))

+2 ∑_{j}[∑_{i}(f(η_{j}η_{i}x) − f(η_{i}η_{j}x))][f(x) − f(η_{j}x)].

Since G is Ricci flat, ∑_{i}(f(η_{j}η_{i}x) − f(η_{i}η_{j}x)) = 0 and therefore

Lρ(x) ≤ X = 2αk ∑_{j}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x)).

Now we consider

Lf^{2}(x) log f^{2}(x) = ∑_{j}[f^{2}(x) log f^{2}(x) − f^{2}(η_{j}x) log f^{2}(η_{j}x)]
= 2 ∑_{j} f(x)[f(x) − f(η_{j}x)] log f^{2}(x)

− ∑_{j}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x))

+ ∑_{j} f(x)f(η_{j}x)[log f^{2}(x) − log f^{2}(η_{j}x)]

= 2kαf^{2}(x) log f^{2}(x)

− ∑_{j}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x))

+ ∑_{j} f(x)f(η_{j}x)[log f^{2}(x) − log f^{2}(η_{j}x)].

We will need to upper bound

∑_{j} f(x)f(η_{j}x)[log f^{2}(x) − log f^{2}(η_{j}x)].

This can be done by maximizing ∑_{i=1}^{k} ab_{i}(log a^{2} − log b_{i}^{2}) subject to ∑_{i=1}^{k} b_{i} = ka − αka log a^{2}. We can then use Lagrange’s method. The maximum is achieved when all b’s are equal. Thus

∑_{j} f(x)f(η_{j}x)[log f^{2}(x) − log f^{2}(η_{j}x)]

≤ kf(x)(f(x) − αf(x) log f^{2}(x)){log f(x) − log(f(x) − αf(x) log f^{2}(x))^{2}}
≤ 2kαf^{2}(x) log f^{2}(x).

Also, we consider a lower bound for

∑_{j}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x)).

We can use the Lagrange method again for minimizing ∑_{i=1}^{k}{(a log a^{2} − b_{i} log b_{i}^{2})(a − b_{i}) − 2(a − b_{i})^{2}}

subject to ∑_{i=1}^{k} b_{i} = ka − αka log a^{2}. Therefore we have

∑_{η_{j}}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x)) − 2 ∑_{j}(f(x) − f(η_{j}x))^{2}

≥ kα^{3}f^{2}(x)| log^{3} f^{2}(x)|.

Combining the above arguments, we have, for any positive σ, the following:

L(∑_{j}[f(x) − f(η_{j}x)]^{2} + σαkf^{2}(x))

≤ 4σα^{2}f^{2}(x) log f^{2}(x) − (σ − 1) ∑_{j}[f(x) log f^{2}(x) − f(η_{j}x) log f^{2}(η_{j}x)](f(x) − f(η_{j}x))
≤ 4σα^{2}f^{2}(x) log f^{2}(x) + (σ − 1)α^{3}f^{2}(x)| log^{3} f^{2}(x)|

−2(σ − 1) ∑_{j}(f(x) − f(η_{j}x))^{2}.

Now we consider a vertex v which achieves the maximum value over all x ∈ S, for

∑_{j}[f(x) − f(η_{j}x)]^{2} + σαkf^{2}(x) log f^{2}(x).

We have

0 ≤ L(∑_{j}[f(v) − f(η_{j}v)]^{2} + σαf^{2}(v))
≤ 4σα^{2}f^{2}(x) log f^{2}(x) + (σ − 1)α^{3}f^{2}(x)| log^{3} f^{2}(x)|

−2(σ − 1) ∑_{j}(f(x) − f(η_{j}x))^{2}

This implies

∑_{j}[f(v) − f(η_{j}v)]^{2} ≤ \frac{2σαk}{σ − 1}f(v) log f^{2}(v)(1 + \frac{α}{4} log^{2} f^{2}(v))

for σ > 1. Therefore for every x ∈ V, we have

∑_{j}[f(x) − f(η_{j}x)]^{2} + σαkf^{2}(x) log f^{2}(x)

≤ kα(\frac{2σ}{σ − 1} + σ)f^{2}(v) log f^{2}(v)(1 + \frac{α}{4} log f^{2}(v))
≤ kα\frac{σ + σ^{2}}{σ − 1} sup_{v} f^{2}(v) log f^{2}(v)(1 + \frac{α}{4} log f^{2}(v))

for any σ > 1. For U = sup |f(x)| ≥ 1, we have

∑_{j}[f(x) − f(η_{j}x)]^{2} ≤ kα\frac{σ + σ^{2}}{σ − 1} max\{U^{2} log U^{2}(1 + \frac{α}{4} log^{2} U^{2}), 1\}.

The proof of Theorem 6 is complete.

By taking σ = 2 in Theorem 6 we have

Corollary 1 In a Ricci flat graph G, suppose a function f : V (G) → ℝ satisfies

Lf(x) = ∑_{j}[f(x) − f(η_{j}x)] = αkf(x) log f^{2}(x).

Then for all x ∈ V (G)

∑_{j}[f(x) − f(η_{j}x)]^{2} ≤ 6αk max\{U^{2} log U^{2}(1 + \frac{α}{4} log U^{2}), 1\}

provided sup_{y} f(y) ≥ 1.

5 Consequences of logarithmic Harnack inequalities for graphs

Theorem 7 In a connected Ricci flat graph G = (V, E), suppose a function f : V → ℝ satisfies the logarithmic Harnack inequality and ∑_{x} f^{2}(x)d_{x} = vol G. Then the log-Sobolev constant α of G

satisfies

α ≥ min(\frac{1}{32kD^{2}} , \frac{1}{24kD^{2} log U^{2}} )

where U = sup_{z} |f(z)|, k denotes the degree and D denotes the diameter of G.

Proof: We consider the following two cases:

Case 1: sup |f − 1| ≤ 1/2. The proof for this case is almost identical to that of Case 1 of the proof of Theorem 4. We omit the proof here and we have

α ≥ \frac{λ_{1}}{4} .

The following eigenvalue lower bound for a Ricci flat graph is given in [6]:

λ_{1} ≥ \frac{1}{8kD^{2}} .  (20)

Therefore we have

α ≥ \frac{1}{32kD^{2}} .

Case 2: sup |f − 1| ≥ 1/2. We consider vertices x_{0}, y_{0} satisfying f(x_{0}) = c and f(y_{0}) = 1. The existence of y_{0} is guaranteed by the fact that

∑_{v} f^{2}(v)d_{x} = vol G.

Let P = (x_{0} = v_{0}, v_{1}, ⋯, v_{s} = y_{0}) denote a shortest path joining x_{0} and y_{0}. Clearly, s ≤ D. We consider the case that f(x_{0}) = sup f and U^{2} log U^{2} ≥ 1. The other case can be dealt with in a similar way. Using the logarithmic Harnack inequality, we have

(f(v_{i}) − f(v_{i+1}))^{2} ≤ 6αkU^{2} log U^{2}
∑_{i=0}^{s−1}(f(v_{i}) − f(v_{i+1}))^{2} ≤ 6αksU^{2} log U^{2} ≤ 6αkDU^{2} log U^{2}.

On the other hand, we have

∑_{i=0}^{s−1}(f(v_{i}) − f(v_{i+1}))^{2} ≥ \frac{1}{D} \{∑_{i=0}^{s−1}(f(v_{i}) − f(v_{i+1}))\}^{2}

≥ \frac{1}{D} (f(x_{0}) − f(y_{0}))^{2}
≥ \frac{(c − 1)^{2}}{D}
≥ \frac{U^{2}}{4D} .

Together we have

α ≥ \frac{1}{24kD^{2} log U^{2}} .

For the case of f(x_{0}) ≤ 1 or U^{2} log U^{2} ≤ 1, the proof for α ≥ \frac{1}{24kD^{2}} is quite similar and we can and will be omitted. This completes the proof of Theorem 7. □

The eigenvalue lower bound given in (20) is sharp and the factor of k is necessary for some homogeneous graphs [6, 4] ( for example, the graph with vertex set Z_{p} × Z_{2} and edge generators (a, b), a ∈ Z_{p}, b ∈ Z_{2}.) It is not difficult to show that the log-Sobolev constant is bounded above by λ_{1}/2 (see [8]). As a consequence of Theorem 6, for a homogeneous graph the lower bounds for the log-Sobolev constant and the eigenvalue λ_{1} can differ by at most a factor of log^{2} U.

The factor of log U can be bounded for certain graphs in terms of an isoperimetric invariant for graphs. We say a graph G = (V, E) has isoperimetric dimension δ with isoperimetric constant c_{δ} if for any subset X of V with vol X ≤ vol G/2, the number of edges leaving X satisfies

|E(X, X̄)| ≥ c_{δ}( vol X)^{1−1/δ}.

For a vertex v in a graph G and an integer r, the r- neighborhood of v, denoted by N_{r}(v) is defined by N_{r}(v) = {u ∈ V : d(u, v) ≤ r} where d(u, v) denotes the distance between u and v. A graph with isoperimetric dimension δ has growth-rate (c, δ) in the following sense [4]:

vol N_{r}(v) ≥ cr^{δ}

where r ≤ D and D denotes the diameter of G. It is not hard to show that a graph with isoperimetric dimension δ has growth-rate (c, δ) where c depends only on the isoperimetric constant c_{δ}. However, graphs with growth-rate (c, δ) do not necessarily have isoperimetric dimension δ (see [4]) and do not in general have good eigenvalue lower bounds. For graphs with isoperimetric dimension δ, we will show that log U is bounded above by δ log δ.

Theorem 8 For a Ricci flat graph with isoperimetric dimension δ, let f denote a function achieving the log-Sobolev constant α with sup_{x} f(x) = U. Then we have either

α ≥ \frac{c_{1}}{k( vol G)^{2/δ}}

or

log U ≤ c_{2}δ log δ

where k denotes the degeree and constants c_{1}, c_{2} depend only on the isoperimetric constant.

Proof: Let P denote a shortest path with vertices x_{0}, ⋯, x_{s} where f(x_{0}) = U and f(x_{s}) ≤ 1. To upper bound U, we consider the ball B_{r} = {y : d(x_{0}, y) ≤ r}. And we consider

s = ⌊\frac{1}{2\sqrt{6αk log U^{2}}} ⌋.

Using Corollary 1, for y ∈ B_{r}, we have

U − f(y) = ∑_{i}[f(x_{i−1}) − f(x_{i})]
≤ sU\sqrt{6αk log U^{2}}
≤ \frac{U}{2}

Therefore we have

vol G ≥ ∑_{x∈B_{s}} f^{2}(x)d_{x} ≥ \frac{U^{2}}{4} vol B_{s}

This implies

\frac{U^{2}}{4} ≤ \frac{vol G}{vol B_{r}} ≤ \frac{vol G}{cs^{δ}}

Substituting for s, we have

α^{δ/2} vol G ≥ \frac{U^{2}}{4c(6k log U^{2})^{δ/2}}  (21)

We consider two subcases: Subcase (a):

\frac{U^{2}}{(log U^{2})^{d/2}} ≥ 1

Then (21) implies

α ≥ \frac{c′}{k( vol G)^{2/δ}}

where c′ = (4c)^{−2/δ}6^{−1}. Subcase (b):

\frac{U^{2}}{(log U^{2})^{δ/2}} < 1

This is equivalent to

log U ≤ \frac{δ}{2} log log U^{2}.

Thus

log U ≤ δ log δ
□

Combining Theorems 7 and 8, we have Theorem 9 In a Ricci flat graph G with isoperimetric dimension δ, the log-Sobolev constant α satisfies

α ≥ min\{\frac{c}{( vol G)^{2/δ}} , \frac{c′}{kD^{2}δ log δ} \}

where k denotes the degree of G, c depends only on the isoperimetric constant, and c′ is an absolute constant.

6 Logarithmic Harnack inequalities for subgraphs

The definition for the log-Sobolev constant for a graph G can be easily generalized to induced subgraphs with boundary conditions. Let S denote a subset of vertices in a graph G and let S^{∗} denote the set of edges with at least one endpoint in S. Let δS denote the vertex boundary of S. The log-Sobolev constant α_{S} for the induced subgraph S with Dirichlet boundary condition can be defined as follows:

α = inf_{f} \frac{∑_{\{x,y\}∈S^{∗}}(f(x) − f(y))^{2}w_{x,y}}{∑_{x∈V} f^{2}(x)d_{x} log \frac{f^{2}(x) vol S}{∑_{z∈S} f^{2}(z)d_{z}}}  (22)

where f ranges over all nontrivial functions f : S ∪ δS → ℝ satisfying f(y) = 0 for y ∈ δS.

Also, the log-Sobolev constant α_{S} for the induced subgraph S with Neumann boundary condition can be defined as follows:

α = inf_{f≠c} \frac{∑_{\{x,y\}∈S^{∗}}(f(x) − f(y))^{2}w_{x,y}}{∑_{x∈V} f^{2}(x)d_{x} log \frac{f^{2}(x) vol S}{∑_{z∈S} f^{2}(z)d_{z}}}  (23)

where f ranges over all non-constant functions f : S ∪ δS → ℝ. Many methods for bounding log-Sobolev constants for graphs can be extended to the log-Sobolev constant for certain subgraphs as well.

Here we state the corresponding theorems on logarithmic Harnack inequalities for certain subgraphs. The proofs are quite similar to the boundaryless case and will be omitted.

Theorem 10 In a k-regular Ricci flat graph G, consider a strongly convex subgraph S of G. Suppose a function f : S ∪ δS → ℝ satisfies the Dirichlet or Neumann boundary condition and achieves the log-Sobolev constant. Also, assume ∑_{x∈S} f^{2}(x)d_{x} = volS. Then the following inequality holds for all

x ∈ S:

∑_{y∼x}[f(x) − f(y)]^{2} ≤ 6kα sup_{z} f^{2}(z) log f^{2}(z)(1 + \frac{α}{4} log f^{2}(z)).

Theorem 11 Let S denote a strongly convex subgraph of a connected Ricci flat graph. Suppose a function f : V → ℝ satisfies the Dirichlet or Neumann boundary condition and achieves the log-Sobolev constant α. Also, assume ∑_{x∈S} f^{2}(x)d_{x} = vol S. Then the log-Sobolev constant α of G

satisfies

α ≥ min(\frac{1}{32kD^{2}} , \frac{1}{24kD^{2} log U^{2}} ),

where U = sup_{z} |f(z)|,, k is the degree, and D denotes the diameter of S.

Here we used the fact that a k-regular Ricci flat graph or a strongly convex subgraph has the

eigenvalue bound λ_{1} ≥ \frac{1}{8kD^{2}} and this lower bound is sharp up to a constant factor (the factor of k is necessary for some homogeneous graphs) [6]. Based on the fact of α ≤ λ_{1}/2 and as a consequence of Theorems 6 and 10, the log-Sobolev constant and the eigenvalue λ_{1} can differ by at most a factor of log U.

For graphs with isoperimetric dimension δ, similar to Theorem 10 the following lower bound for α holds in terms of δ.

Theorem 12 Let S denote a strongly convex subgraph of a Ricci flat graph with isoperimetric dimension δ. Suppose a function f : V → ℝ satisfies the Dirichlet or Neumann boundary condition and achieves the log-Sobolev constant. Then the log-Sobolev constant α of G satisfies

α ≥ min(\frac{c}{k( vol S)^{δ/2}} , \frac{c′}{kD^{2}δ log δ}),

where k is the degree, and D denotes the diameter of S, and c is a constant depending only on the isoperimetric constant and c′ denotes some absolute constant.

References

[1] D. Bakry, L’hypercontractivité et son utilisation en théorie des semigroups, In Ecole d’ été de Saint Flour 1992, Springer LNM 1581.

[2] W. Beckner, Inequalities in fourier analysis, Annals of Mathematics 102 (1975) 159-182.

[3] F. R. K. Chung and S. -T. Yau, Eigenvalues of graphs and Sobolev inequalities, Combinatorics, Probability and Computing, 4 (1995) 11-26.

[4] F. R. K. Chung, Spectral Graph Theory, CBMS Lecture Notes, 1996 , AMS Publication.

[5] F. R. K. Chung, Logarithmic Sobolev techniques for random walks on graphs, preprint.

[6] F.R.K. Chung and S.-T. Yau, A Harnack inequality for homogeneous graphs and subgraphs, Communications in Analysis and Geometry, 2 (1994), 628-639.

[7] J.-D. Deuschel and D.W. Stroock, Hypercontractivity and spectral gap of symmetric diffusions with applications to the stochastic Ising models, J. Funct. Anal. 92 (1990), 30-48.

[8] P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, preprint.

[9] L. Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97, (1976) 1061-1083.

[10] O.S. Rothaus, Logarithmic Sobolev inequalities and the spectrum of Schrödinger operator, j. Funct. Anal. 42 (1981), 110-120.

[11] A.J. Sinclair, Algorithms for Random Generation and Counting, Birkhauser, 1993.

[12] D. Stroock, Logarithmic Sobolev inequalities for Gibbs states, in Lecture Notes in Math. (1993) Springer LNM 1563.

[13] S. T. Yau and Richard M. Schoen, Differential Geometry, International Press, Cambridge, Massachusetts, 1994.