A Harnack inequality for Dirichlet eigenvalues ^{∗}

Fan Chung University of California at San Diego La Jolla, CA 92093

S.-T. Yau Harvard University Cambridge, Massachusetts 02138

Abstract We prove a Harnack inequality for Dirichlet eigenfunctions of abelian homogeneous graphs and their convex subgraphs. We derive lower bounds for Dirichlet eigenvalues using the Harnack inequality. We also consider a randomization problem in connection with combinatorial games using Dirichlet eigenvalues.

1 Introduction

In a graph G, for a subset S of the vertex set V = V (G), the induced subgraph determined by S has edge set consisting of all edges of G with both endpoints in S. There are two types of boundaries. The (vertex) boundary δS of an induced subgraph S consists of all vertices that are not in S and are adjacent to some vertices in S. The edge boundary, denoted by ∂S consists of all edges containing one endpoint in S and one endpoint not in S, but in the “host” graph. The host graph can be regarded as a special case of a graph with no boundary. We will also use S to denote the induced subgraph on S, if there is no danger of confusion.

For an induced subgraph S with non-empty boundary, there are, in general, two kinds of eigenvalues — the Dirichlet eigenvalues and the Neumann eigenvalues, subject to different boundary conditions. Neumann eigenvalues are discussed in [3, 4] in connection with random walk problems. We consider the Dirichlet eigenvalues here. And we consider the family of functions satisfying f(x) = 0 for any vertex x in the vertex boundary δS ( which is called the Dirichlet boundary condition).

One approach for controlling the behavior of eigenfunctions is the Harnack inequality: In [2], it was showed that for every vertex x in an abelian homogeneous graph G, any eigenfunction f with eigenvalue λ satisfies

∗Journal of Graph Theory, to appear.

∑_{\begin{matrix}y \\ x∼y \end{matrix}} (f(x) − f(y))^{2} ≤ ckλ max_{z} f^{2}(z)  (1)

where x ∼ y denotes x and y are adjacent in G, k denotes the degree of x and c denotes some absolute constant. However, the above inequality does not hold for general graphs. For example, a graph formed by joining two complete graphs of the same size by one edge is a counter example.

In this paper, we define a natural notion of convexity for subgraphs (which is different from and somewhat weaker than strong convexity as in [3, 4]). (The detailed definition will be given in the next section.) We will show that for convex subgraphs of an abelian homogeneous graph, a variation of the above Harnack inequality for Dirichlet eigenvalues holds. We will use this Harnack inequality to derive lower bounds for eigenvalues in terms of the diameter and degree of the convex subgraph. In addition, we use Dirichlet eigenvalues to deal with a randomized game which can be formulated as a boundary condition problem.

2 Laplacian and convexity

Let Γ = (V, E) denote a graph with vertex set V = V (Γ) and edge set E = E(Γ). Suppose a group H acts on V such that:

(i) for all g ∈ H, {gu, gv} ∈ E if and only if {u, v} ∈ E, (ii) for any two vertices u and v, there is a g ∈ H such that gu = v.

Then we say Γ is a homogeneous graph with the associated group H. In other words, Γ is vertex-transitive under the action of H and we can identify V with the coset space H/I where I = {g ∈ H : gv = v} , for a fixed vertex v, denotes the isotropy group. We note that the Cayley graph is a special case of homogeneous graphs with I trivial. The edge set of a homogeneous graph Γ can be described by an (edge) generating set K ⊂ H so that each edge of Γ is of the form {v, gv} for some v ∈ V, and g ∈ K. In this paper we require the generating set K to be symmetric, i.e., g ∈ K if and only if g^{−1} ∈ K. If H is abelian, we say Γ is an abelian homogeneous graph.

The Laplacian L of a homogeneous graph Γ acts on the space of functions f : V (Γ) → ℝ as follows:

Lf(x) = \frac{1}{k} ∑_{g∈K}(f(x) − f(gx))  (2)

where k denotes the degree in Γ. The Dirichlet eigenvalues of an induced subgraph S of G is defined by:

λ = inf_{\begin{matrix}f≠0 \\ f∈D^{∗} \end{matrix}} \frac{∑_{\{x,y\}∈S∪∂S}(f(x) − f(y))^{2}}{k ∑_{x∈S} f^{2}(x)}  (3)

Various properties of Laplacians and eigenvalues for graphs can be found in [1]. An induced subgraph S of a graph G with vertex boundary δS is said to be convex if for any subset X ⊂ δS, its neighborhood N(X) = {y : y ∼ x ∈ X} satisfies

|N(X) \ (S ∪ δS)| = |{y ∉ S ∪ δS : y ∼ x ∈ X}| ≥ |X|  (4)

where we write y ∼ x if y is adjacent to x. In other words, any subset X of the boundary δS of S has at least as many neighbors outside of S ∪ δS as the cardinality of X. We will call (4) the boundary expansion property.

Lemma 1 If two induced subgraphs F_{1}, F_{2} are both convex, then the induced subgraph of F_{1} ∩ F_{2} is convex.

Proof: Suppose X ⊂ δ(F_{1} ∩F_{2}). We can partition X into two parts X_{1} = X ∩δF_{1} and X_{2} = X \ δF_{1}. Clearly X_{2} is contained F_{1}. Since F_{1} and F_{2} have the boundary expansion property, we have

|N(X_{1}) \ (F_{1} ∪ δF_{1})| ≥ |X_{1}|
|N(X_{2}) \ (F_{2} ∪ δF_{2})| ≥ |X_{2}|

where N(X) = {y : y ∼ x ∈ X}. Since N(X_{2}) \ F_{2} ⊂ F_{1} ∪ δF_{1}, therefore we have

N(X_{2}) \ (F_{2} ∪ δF_{2}) ∩ (δ(X_{1}) \ (F_{1} ∪ δF_{1})) = ∅

Hence

|N(X) \ (F_{1} ∩ F_{2} ∪ δ(F_{1} ∩ F_{2})| ≥ |δ(X_{1}) \(F_{1} ∪ δF_{1})| + |δ(X_{2}) \ (F_{2} ∪ δF_{2})|
≥ |X_{1}| + |X_{2}| = |X|

and the proof is completed. □

Example 2 We consider the space S of all m×n matrices with non-negative integral entries having column sums c_{1}, …, c_{n}, and row sums r_{1}, … r_{m}. First, we construct a homogeneous graph Γ with the vertex set consisting of all m × n matrices with integral (possibly negative) entries. Two vertices u and v are adjacent if they differ at four entries in some submatrix determined by two columns i, j and rows k, m satisfying

u_{ik} = v_{ik} + 1, u_{jk} = v_{jk} − 1, u_{im} = v_{im} − 1, u_{jm} = v_{jm} + 1

It is easy to see that Γ is a homogeneous graph with the edge generating set consisting of all 2 × 2 submatrices ( \begin{matrix}1 & −1 \\ −1 & 1 \end{matrix} ). It is easy to see that S is just the intersection of convex subgraphs that are halfplanes. Each of the halfplanes consists of matrices with (i, j)th entry non-negative for some i and j.

3 Harnack inequalities for Dirichlet eigenvalues

Lemma 3 For a convex subgraph S of a graph G, a function f : S ∪ δS → ℝ satisfying

∑_{\begin{matrix}y \\ y∼x \end{matrix}}(f(x) − f(y)) = λf(x)d_{x}

for x ∈ S and f(x) = 0 for x ∈ δS, can be extended to all vertices of G which are adjacent to some vertex in S ∪ δS such that f(z), for x ∈ S ∪ δS, satisfies

∑_{\begin{matrix}y \\ y∼z \end{matrix}}(f(z) − f(y)) = λf(z)d_{z}

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

Proof: To extend f for all vertices adjacent to some vertices in S ∪ δS, we consider a system of |δS| equations:

∑_{\begin{matrix}y \\ y∼x \end{matrix}}(f(x) − f(y)) = 0

for each x ∈ δS. The variables are f(z) for every z ∉ S ∪ δS and z ∼ y ∈ S ∪ δS. The boundary expansion condition guarantees that any m equations involve at least m variables. Therefore, there are solutions for f(y) for all y adjacent to some vertex in S ∪ δS. □

Theorem 4 Suppose S is a finite convex subgraph in an abelian homogeneous graph Γ associated with an abelian group and the edge generating set K consisting of k generators. Let f : S → ℝ denote an eigenfunction associated with Dirichlet eigenvalue λ. Then the following inequality holds for x ∈ S, a ∈ K and ax ∈ S:

[f(x) − f(ax)]^{2} + kαλf^{2}(x) ≤ \frac{kλα^{2}}{α − 2} sup_{y∈S} f^{2}(y)

for any α > 2.

Proof: Using Lemma 3, we can extend f to all vertices adjacent to some vertices in S ∪ δS. Then, we consider, for some g ∈ K,

ϕ_{g}(x) = [f(x) − f(gx)]^{2} + kαλf^{2}(x)

Suppose ϕ_{a}(z) achieving the maximum value of ϕ_{g}(x) ranging over all g ∈ K, x ∈ S. Since for a vertex x in δS, ϕ_{g}(x) ≤ ϕ_{g}(y) for some neighbor y ∈ S of x, we have ϕ_{g}(x) ≤ ϕ_{a}(z) for all x ∈ δS ∪ S. Let ϕ(x) denote ϕ_{a}(x). We consider

Lϕ(x) = \frac{1}{k} ∑_{b∈K}[ϕ(x) − ϕ(bx)]
≤ \frac{1}{k} ∑_{b∈K}[(f(x) − f(ax))^{2} − (f(bx) − f(abx))^{2}] + αλ ∑_{b∈K}[f^{2}(x) − f^{2}(bx)]
= Y + Z

where

Y = \frac{1}{k} ∑_{b∈K}[(f(x) − f(ax))^{2} − (f(bx) − f(abx))^{2}]
= \frac{2}{k} ∑_{b∈K}(f(x) − f(ax) − f(bx) + f(abx))(f(x) − f(ax)

−\frac{1}{k} ∑_{b∈K}(f(x) − f(ax) − f(bx) + f(abx))^{2}

≤ \frac{2}{k} \{∑_{b∈K}[f(x) − f(bx)] − ∑_{b∈K}[f(ax) − f(abx)]\}(f(x) − f(ax))
≤ 2λ[f(x) − f(ax)]^{2}

and,

Z = αλ ∑_{b∈K}[f^{2}(x) − f^{2}(bx)]
≤ 2αλ{∑_{b∈K}[f(x) − f(bx)]f(x) − ∑_{b∈K}[f(x) − f(bx)]^{2}}
≤ 2αλ{kλf^{2}(x) − ∑_{b∈K}[f(x) − f(bx)]^{2}}

Therefore, we have

0 ≤ Lϕ(z) ≤ 2kαλ^{2}f^{2}(z) − λ(α − 2) ∑_{a∈K}[f(v) − f(av)]^{2}

and

[f(z) − f(az)]^{2} ≤ \frac{2kλα}{α − 2}f^{2}(z)

for α > 2. Therefore for all x ∈ S, g ∈ K, gx ∈ S, we have

[f(x) − f(gx)]^{2} + kαλf^{2}(x) ≤ [f(z) − f(az)]^{2} + kαλf^{2}(z)
≤ \frac{2kλα}{α − 2}f^{2}(z) + kαλf^{2}(z)
≤ (\frac{2α}{α − 2} + α)λkf^{2}(z)
= \frac{α^{2} λ k}{α − 2} max_{y∈S} f^{2}(y)

for any α > 2. The proof of Theorem 4 is complete. □

By taking α = 4 in Theorem 4 we have

Theorem 5 Suppose S is a convex subgraph in an abelian homogeneous graph Γ with edge generating set K consisting of k generators. Let f : S → ℝ denote an eigenfunction associated with Dirichlet eigenvalue λ. Then for all x ∈ S, a ∈ K, we have

[f(x) − f(ax)]^{2} ≤ 8kλ sup_{y∈S} f^{2}(y).

4 Eigenvalues and diameters

The Harnack inequality in previous sections can be used to derive the following eigenvalue inequality:

Theorem 6 The Dirichlet eigenvalue λ of a convex subgraph S of an abelian homogeneous graph Γ satisfies

λ ≥ \frac{1}{8kD^{2}}

where k is the degree of Γ and D is the diameter of S.

Proof: Let f denote an eigenfunction defined on S achieving λ. We can choose f such that

sup_{x∈S} |f(x)| = 1 = sup_{x∈S} f(x)

Let u denote a vertex with f(u) = max_{x∈S} f(x) = 1 and let v denote a vertex v ∈ S ∪ δS with f(v) ≤ 0. We now consider a shortest path P in S joining u and v. Suppose P has vertices (u = v_{0}, v_{1}, ⋯, v_{t} = v) where v_{i} is adjacent to v_{i+1}. Since the diameter of S is D, we have t ≤ D.

We consider

X = ∑_{i=0}^{t−1}[f(v_{i}) − f(v_{i+1})]^{2}.

By Theorem 6, we have

X ≤ 8kλD.

On the other hand, we have

X = ∑_{i=0}^{t−1}[f(v_{i}) − f(v_{i+1})]^{2}
≥ \frac{1}{D} (f(u) − f(v))^{2}
≥ \frac{1}{D}

Therefore we obtain

λ ≥ \frac{1}{8kD^{2}}

This completes the proof of Theorem 7. □

5 A randomization problem and Richman games

We consider the following two-player game, which is a variation of the Richman game [5]. The game involves a given graph G in which two special vertices are colored, one in blue and one in red. In addition, there is one pebble that is placed at one vertex of G. At each turn, the two players, Bob and Rose, flip a fair coin for the right to move the pebble to an adjacent vertex. If the pebble reaches the blue vertex first, then Bob wins. If the pebble reaches the red vertex first, then Rose wins. The game is a draw if neither special vertex is ever reached. A natural question is to determine the optimal strategy to maximize their probability of winning from any initial position of the pebble. Several different versions of this game are examined in [5, 6]. For example, instead of taking turns or flipping a coin, the two players repeatedly bid for the right to make the next move. In this section, we consider the following randomization problem which was first proposed by Joel Spencer [7].

In a graph G and a subset S ⊂ V (G), we consider a coloring of the vertices in the boundary δS in either blue or red. Suppose we take a random walk W_{x} = (v_{0}, v_{1}, …), starting from v_{0} = x and moving from v_{i} to its neighbor v_{i+1} with equal probability. What is the probability p(x) that W_{x} hits a blue boundary vertex before a red boundary vertex?

For an induced subgraph S with non-empty vertex boundary δS, suppose σ is a real-valued function defined on δS. We consider the family F_{σ} of functions which assume the same values as σ for vertices in δS.

F_{σ} = {f : S ∪ δS → ℝ, f|_{δS} = σ}

We consider the following Dirichlet sum for a function f in F_{σ}.:

Φ(f) = ∑_{{x,y}∈S∪∂S}(f(x) − f(y))^{2}

In particular, we consider f_{∗} which achieves the minimum value of Φ over all functions in F_{σ}.

Lemma 7 Suppose

Φ(f_{∗}) = inf_{f∈F_{σ}} Φ(f).

Then f_{∗} satisfies the following:

(i) For any x ∈ S,

∑_{\begin{matrix}y \\ y∼x \end{matrix}}(f_{∗}(x) − f_{∗}(y)) = 0

(ii) For any x ∈ S,

inf_{y∈δS} σ(y) ≤ f_{∗}(x) ≤ sup_{y∈δS} σ(y)

(iii) Suppose the induced subgraph on S is connected and σ ≠ 0. Then for any x ∈ S,

inf_{y∈δS} σ(y) < f_{∗}(x) < sup_{y∈δS} σ(y)

Proof: The proof of (i) follows from a standard variational argument. (ii) can be proved by using the maximal principle. To see (iii), we consider the set S_{0} = {v : f_{0}(v) = inf_{y∈δS} σ(y)}. It is not hard to check that S_{0} must be the entire connected component of S. □

We consider

D_{∗} = {h : S ∪ δS → ℝ, h|_{δS} = 0.}

For each function f ∈ F_{σ}, we have f − f^{∗} ∈ D_{∗}. Thus, each function f can be expressed as:

f = f_{∗} + g

where g is in D_{∗}.

For any function f in F_{σ}, we consider the following operator:

−Δf(x) = \frac{1}{d}_{x} ∑_{\begin{matrix}y \\ y∼x \end{matrix}}(f(x) − f(y))

for any x ∈ S and d_{x} denotes the degree of x in G.

We remark that −Δ is equal to the Laplacian L for regular graphs. For a general graph, −Δ is not self-adjoint but it is related to the self-adjoint operator L, i.e., −Δ = T^{1/2}LT^{−1/2} where T is a diagonal matrix with the (v, v)-entry having value d_{v}.

Lemma 8 Suppose a function f ∈ F_{σ} is the sum f = f_{∗} + g for a function g ∈ D_{∗} and f_{∗} achieving the minimum of Φ. Then we have

(I + ϵΔ)f(x) = f_{∗}(x) + (1 + ϵΔ)g(x)

for any x in S where ϵ is real and I denotes the identity operator.

The proof is straightforward and will be omitted.

Now, we consider the problem of determining p(x).

Theorem 9 For a connected induced subgraph S in a graph, we consider the boundary function σ satisfying σ(x) = 1 if x is colored blue and 0, if x is in red. Let f_{∗} be the function defined on S ∪ δS with boundary condition σ and f_{∗} minimizes Φ. Then

p(x) = f_{∗}(x)

for x ∈ S.

Proof: We note that p satisfies the boundary function σ. Furthermore, for x ∈ S, we have

p(x) = \frac{1}{d_{x}} ∑_{y∼x} p(y).

From Lemma 7 (i), f_{∗} satisfies the same recurrence. We consider g = p − f_{∗} which assume values 0 at δS. We consider the set M of vertices v in S satisfying g(x) = sup{g(z) : z ∈ S}. If M is not equal to S, let y be a vertex not in S but adjacent to some vertex in S. Since for x in M, g(x) = \frac{1}{d_{x}} ∑_{y∼x} g(y) , we have g(y) = g(x). Since S is connected, this implies that M = S and g = 0. Therefore p(x) = f_{∗}(x) for all x in S. □

Here we describe a recursive process which generates a close approximation of p. Let ϵ denote a positive constant less than 1/2. We start with an arbitrary f_{0} which assumes the same value as σ on δS and 0 in S. We define

f_{s}(x) = \{ \begin{matrix}(I + ϵΔ)f_{s−1}(x) & if x ∈ S \\ σ(x) & if x ∈ δS \end{matrix}

By Lemma 8, we have

f_{t}(x) = f_{∗}(x) + (1 + ϵΔ)^{t}g(x)

for g = f_{0} − f_{∗} in D_{∗}. From Lemma 7, we have 0 ≤ |g(x)| ≤ 1 for x ∈ S. Thus, we have

|f_{t}(x) − f_{∗}(x)| ≤ (1 − ϵλ)^{t}\sqrt{|S|}
≤ e^{−c}

if

t ≥ \frac{c}{ϵλ} log |S|.  (5)

where λ denotes the least Dirichlet eigenvalues of L.

References

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

[2] 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.

[3] F. R. K. Chung and S. -T. Yau, Eigenvalue inequalities for graphs and convex subgraphs, . Communications in Analysis and Geometry, to appear.

[4] F. R. K. Chung, R. L. Graham and S. -T. Yau, On sampling with Markov chains, Random Structures and Algorithms, 9 (1996), 55-78.

[5] A. J. Lazarus, D. E. Loeb, J. G. Propp and D. Ullman, Richman games, Games of no chance, MSRI Publ. 29, Cambridge Univ. Press, Cambridge, 1996, 439-449.

[6] A. J. Lazarus, D. E. Loeb, J. G. Propp and D. Ullman, Richman games under auction play, preprint.

[7] J. Spencer, personal communication.

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