Eigenvalues of graphs and Sobolev inequalities ^{∗}

F. R. K. Chung University of Pennsylvania Philadelphia, Pennsylvaina 19104

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

Abstract We derive bounds for eigenvalues of the Laplacian of graphs using the

discrete versions of the Sobolev inequalities and heat kernel estimates.

1 Introduction

In a graph G with vertex set V (G) and edge set E(G), we define the volume of a subset X of V (G), denoted by vol (X), to be the sum of the degrees of vertices in X, i. e.,

vol(X) := ∑_{v∈X} d_{v}

where d_{v} denotes the degree of the vertex v. We note that the volume of G is vol(V (G)) = vol(G), which is just twice the number of edges in G.

We say that a graph G has isoperimetric dimension δ with an isoperimetric constant c_{δ} if for every subset X of V (G), the number of edges between X and the complement X̄ of X, denoted by |E(X, X̄)| , satisfies

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

where we assume vol(X) ≤ vol(X̄) and c_{δ} is a constant depending only on δ.

Let 0 = λ_{0} ≤ λ_{1} ≤ … ≤ λ_{n−1} denote the eigenvalues of the Laplacian of G (described in detail in Section 2). We will show that

∑_{i≠0} e^{−λ_{i}t} ≤ c\frac{vol(G)}{t^{δ/2}}  (2)

∗Appeared in Combinatorics, Probability and Computing 4 (1995) 11-26.

and

λ_{k} ≥ c′ (\frac{k}{(vol(G))})^{\frac{2}{δ}}  (3)

for suitable constants c and c′ which depend only on δ.

To prove this, we will use the following discrete versions of the Sobolev inequalities (proved in Section 3): For any function f : V (G) → R,

(i) For δ > 1,

∑_{u∼v} |f(u) − f(v)| ≥ c_{δ} \frac{δ − 1}{δ} min_{m}(∑_{v} |f(v) − m|^{\frac{δ}{δ−1}} d_{v})^{\frac{δ−1}{δ}}

(ii) For δ > 2,

(∑_{u∼v} |f(u) − f(v)|^{2})^{1/2} ≥ c_{δ} \frac{(δ − 1)^{3/2}}{2δ^{3/2}} min_{m}(∑_{v} |f(v) − m|^{α}d_{v})^{\frac{1}{α}}

where α = \frac{2δ}{δ−2}, and u ∼ v means that u and v are adjacent in G.

The proofs here are intimately related to techniques of estimating eigenvalues of Riemannian manifolds which can be traced back to the work of Nash [?]. Nevertheless, this paper is self-contained and entirely graph theoretic.^{1} In a sense, a graph can be viewed as a discretization of a Riemannian manifold in ℝ^{n} where n is roughly equal to δ. The eigenvalue bound in (3) is an analogue of the Polya conjecture [?] for Dirichlet eigenvalues of regular domains M in ℝ^{n}:

λ_{k} ≥ \frac{2π}{w_{n}} (\frac{k}{volM} )^{2/n}

where w_{n} is the volume of the unit disc in ℝ^{n}.

There have been many papers [?, ?, ?, ?, ?] contributing to bridging the continuous notion of eigenvalues for manifolds (which has been extensively studied) and the discrete notion of eigenvalues for graphs (which occurred in numerous applications in approximation and randomized algorithms). Previous work has been mostly concerned with regular graphs or homogeneous graphs. In this paper, we consider Laplacians of general graphs and obtain eigenvalue estimates in terms of the isoperimetric dimension using the same methods as the continuous case. On one hand, graphs and Riemannian manifolds are quite different objects. Indeed, many of the theorems and proofs in differential geometry are very difficult to translate into similar ones for graphs (since there are no highorder derivatives on a graph). In fact, some of the statements of the theorems in the continuous cases are obviously not true for the discrete (cf. [?] for more discussion). On the other hand, there is a great deal of overlap between these two different areas both in the concepts and methods. Some selected techniques in the continuous case can often be successfully carried out in the discrete setting. The main objective of this paper is to illustrate the effectiveness of the methods of Sobolev inequalities and the heat kernel in spectral graph theory. We remark that in the opposite direction, some eigenvalue bounds for graphs can be translated into new eigenvalue inequalities for Riemannian manifolds. This will be treated in a separate paper [?].

1For undefined graph-theoretical terminology, the reader is referred to [?]

A closely related isoperimetric invariant [?] is the Cheeger constant h(G) of a graph G:

h(G) := min_{X⊆V (G)} \frac{E(X, X̄)}{vol(X)}

where vol(X) ≤ vol(X̄).

In fact, the Cheeger constant can be viewed as a special case of the isoperimetric constant c_{δ} with δ = ∞. It is not difficult to show that the discrete analogue of Cheeger’s inequality holds (cf. [?] for regular graphs, and [?] for general graphs):

2h ≥ λ_{1} ≥ \frac{h^{2}}{2} .

Using a result of Gromov [?] on the growth rate of finitely generated groups, Varopoulos [?] showed that a locally finite Cayley graph of an infinite group γ with a nilpotent subgroup of finite index has isoperimetric dimension δ depending only on the structure of γ. Diaconis and Saloff-Coste [?] applied these results to bound the rate of convergence for random walks on finite nilpotent quotient groups.

2 Preliminaries

Let v_{1}, ⋯, v_{n} denote the vertices of a graph G and let d_{i} denote the degree of v_{i}. Here we assume G contains no loops or multiple edges. Generalizations for weighted undirected graphs will be considered later in Section 5. We define the matrix L as follows:

L(i, j) = \{ \begin{matrix}d_{i} & if i = j \\ −1 & if i and j are adjacent \\ 0 & otherwise \end{matrix}

Let S denote the diagonal matrix with the (i, i)-th entry having value \frac{1}{\sqrt{d_{i}}}. The

Laplacian of G is defined to be

L = SLS.

In other words, we have

L(i, j) = \{ \begin{matrix}1 & if i = j \\ −\frac{1}{\sqrt{d_{i}d_{j}}} & if i and j are adjacent \\ 0 & otherwise \end{matrix}

The eigenvalues of L are denoted by 0 = λ_{0} ≤ λ_{1} ≤ ⋯ ≤ λ_{n−1}. When G is k-regular, it is easy to see that

L = I − \frac{1}{k} A

where A is the adjacency matrix of G.

Let h denote a function which assigns to each vertex v of G a complex value h(v). Then

\frac{⟨h, Lh⟩}{⟨h, h⟩} = \frac{⟨h, SLSh⟩}{⟨h, h⟩}
= \frac{⟨f, Lf⟩}{⟨S^{−1}f, S^{−1}f⟩}

= \frac{∑_{u∼v}(f(u) − f(v))^{2}}{∑_{v} d_{v}f(v)^{2}}  (4)

where h = S^{−1}f.

Let 1 denote the constant function which assumes value 1 on each vertex. Then S^{−1}1 is an eigenfunction of L with eigenvalue 0. Also,

λ_{1} = min_{f⊥S^{−2}1} \frac{∑_{u∼v}(f(u) − f(v))^{2}}{∑_{v} d_{v}f(v)^{2}}  (5)

= min_{f} max_{m} \frac{∑_{u∼v}(f(u) − f(v))^{2}}{∑_{v} d_{v}(f(v) − m)^{2}}  (6)

Lemma 1.

(i)

∑_{i} λ_{i} = n

(ii) For a graph G on n vertices,

λ_{i} ≤ \frac{n}{n − 1}.

Equality holds if and only if G is the complete graph on n vertices.

(iii) For a graph which is not a complete graph, we have λ_{1} ≤ 1.

Proof: (i) follows from considering the trace of L. To see (ii), we consider the following function, for a fixed vertex v_{0} in G,

f_{1}(v) = \{ \begin{matrix}1 & if v = v_{0} \\ 0 & otherwise \end{matrix}

By taking c = \frac{d_{v_{0}}}{∑_{v} d_{v}}, we obtain (ii) using (6).

Suppose G contains two nonadjacent vertices a and b, and consider

f_{2}(v) = \{ \begin{matrix}d_{b} & if v = a \\ −d_{a} & if v = b \\ 0 & if v ≠ a, b. \end{matrix}

(iii) then follows from (4). Remarks on Laplacians and random walks

One of the most common models for random walks on graphs uses the rule of moving from a vertex to all its neighbors with equal probability. This stochastic process can be described by the matrix P satisfying

P f(v) = ∑_{\begin{matrix}u \\ u∼v \end{matrix}} \frac{1}{d_{u}} f(u)

for any f : V (G) → R.

It is easy to check that

P = I − SLS^{−1}.

Therefore, the Laplacian and its eigenvalues have direct implications for random walks on graphs. Further discussions of Laplacians and irreducible reversible Markov chains will be included in Section 5.

3 Sobolev’s inequalities

We will first prove the following.

Theorem 1 In a connected graph G with isoperimetric dimension δ and isoperimetric constant c_{δ}, for an arbitrary function f : V (G) → ℝ, let m denote the smallest value such that

∑_{\begin{matrix}v \\ f(v)<m \end{matrix}} d_{v} ≥ ∑_{\begin{matrix}u \\ f(u)≥m \end{matrix}} d_{u}

Then

∑_{u∼v} |f(u) − f(v)| ≥ c_{δ} \frac{δ − 1}{δ}(∑_{v} |f(v) − m|^{\frac{δ}{δ−1}} d_{v})^{\frac{δ−1}{δ}} .

Here we state two useful corollaries. The first one is an immediate consequence of Theorem 1 and the second one follows from the proof of Theorem 1. Corollary 1: In a connected graph G with isoperimetric dimension δ and isoperimetric constant c_{δ}, an arbitrary function f : V (G) → ℝ satisfies

∑_{u∼v} |f(u) − f(v)| ≥ c_{δ} \frac{δ − 1}{δ} min_{m}(∑_{v} |f(v) − m|^{\frac{δ}{δ−1}} d_{v})^{\frac{δ−1}{δ}} .

Corollary 2: In a connected graph G with isoperimetric dimension δ and isoperimetric constant c_{δ}, for a function f : V (G) → ℝ and a vertex w, define

f_{w}(v) = \{ \begin{matrix}min\{f(v), f(w)\} & if f(w) < m \\ max\{f(v), f(w)\} & if f(w) ≥ m \end{matrix}

where m is as defined in Theorem 1. Then

∑_{u∼v} |f_{w}(u) − f_{w}(v)| + a_{w}(f(w) − m) ≥ c_{δ} \frac{δ − 1}{δ}( ∑_{v∈S_{w}} |f(v) − m|^{\frac{δ}{δ−1}} )^{\frac{δ−1}{δ}}

where

a_{w} = |{u, v} ∈ E(G) : f(u) ≤ f(w) < f(u)}

and

S_{w} = \{ \begin{matrix}\{v : f(v) ≥ f(w) & if f(w) ≥ m\} \\ \{u : f(v) ≤ f(w) & if f(w) < m\} \end{matrix}

Roughly speaking, the proof of Theorem 1 is just a discrete version of “integration by parts” and by using the definition of δ repeatedly, although the precise proof is somewhat lengthy. Proof of Theorem 1:

For a given function f : V (G) → ℝ, we label the vertices so as to satisfy

f(v_{1}) ≤ f(v_{2}) ≤ ⋯ ≤ f(v_{n}).

We define A_{i} = {{v_{j}, v_{k}} ∈ E(G) : j ≤ i < k} and a_{i} = |A_{i}|. We will

write f(i) = f(v_{i}) and d_{i} = d_{v_{i}}. Define S_{i}^{−} = ∑_{j≤i} d_{j} , S_{i}^{+} = ∑_{j>i} d_{j} and

S_{i} = min{S_{i}^{−}, S_{i}^{+}}. Clearly, S_{i} = S_{i}^{+} for f(i) ≥ m and S_{i} = S_{i}^{−} for f(i) < m. We use the convention that S_{0} = S_{n} = 0.

Let h(i) = h(v_{i}) = f(v_{i}) − m, and suppose f(w) = m = f(i_{0}). Then

∑_{u∼v} |h(u) − h(v)| = ∑_{i} a_{i}(h(i + 1) − h(i))
≥ c_{δ} ∑_{i} Si^{\frac{δ−1}{δ}} (h(i + 1) − h(i))

≥ c_{δ} ∑_{i<i_{0}} |h(i)|(S \frac{δ−1}{δ} ; i − S \frac{δ−1}{δ} ; i−1 )

+c_{δ} ∑_{i≥i_{0}} |h(i + 1)|(S \frac{δ−1}{δ} ; i − S \frac{δ−1}{δ} ; i+1 )

= c_{δ} ∑_{i<i_{0}} |h(i)|((S_{i−1} + d_{i})^{\frac{δ−1}{δ}} − S \frac{δ−1}{δ} ; i−1 )

+c_{δ} ∑_{i≥i_{0}} |h(i + 1)|((S_{i+1} + d_{i})^{\frac{δ−1}{δ}} − S \frac{δ−1}{δ} ; i+1 )

≥ c_{δ} ∑_{i<i_{0}} |h(i)|\frac{δ − 1}{δ} · \frac{d_{i}}{Si^{\frac{1}{δ}}} + c_{δ} ∑_{i≥i_{0}} |h(i)|\frac{δ − 1}{δ} · \frac{d_{i}}{Si^{\frac{1}{δ}}}

≥ c_{δ} \frac{δ − 1}{δ} (∑_{i<i_{0}} \frac{|h(i)|^{\frac{δ}{δ−1}} d_{i}}{(|h(i)|^{\frac{δ}{δ−1}} S_{i})^{1/δ}} + ∑_{i≥i_{0}} \frac{|h(v_{i})|^{\frac{δ}{δ−1}} d_{i}}{(|h(v_{i})|^{\frac{δ}{δ−1}} S_{i})^{1/δ}} )

≥ c_{δ} \frac{δ − 1}{δ} (\frac{∑_{i<i_{0}} |h(i)|^{\frac{δ}{δ−1}} d_{i}}{(∑_{i<i_{0}} |h(i)|^{\frac{δ}{δ−1}} d_{i})^{1/δ}} + \frac{∑_{i≥i_{0}} |h(i)|^{\frac{δ}{δ−1}} d_{i}}{(∑_{i≥i_{0}} |h(i)|^{\frac{δ}{δ−1}} d_{i})^{1/δ}} )

≥ c_{δ} \frac{δ − 1}{δ} ((∑_{i<i_{0}} |h(i)|^{\frac{δ}{δ−1}} d_{i})^{\frac{δ−1}{δ}} + (∑_{i≥i_{0}} |h(i)|^{\frac{δ}{δ−1}} d_{i})^{\frac{δ−1}{δ}} )

≥ c_{δ} \frac{δ − 1}{δ} (∑_{i} |h(i)|^{\frac{δ}{δ−1}} d_{i})^{\frac{δ−1}{δ}}

Therefore Theorem 1 is proved.

We remark that Corollary 2 follows from the fact that for f(w) < m,

∑_{u∼v} |f_{w}(u) − f_{w}(v)| = ∑_{\begin{matrix}i \\ f(i)<f(w) \end{matrix}} a_{i}(h(i + 1) − h(i))

≥ ∑_{\begin{matrix}i \\ h(i)<h(w) \end{matrix}} |h(i)|(a_{i} − a_{i−1}) − a_{w}|h(w)|

Before we proceed to prove the following Sobolev inequality, here we briefly describe the main idea of the proof. Although the proof of Theorem 2 is more complicated than that of Theorem 1, the proof consists of two applications of the discrete version of “integration by parts”, together with an application of Theorem 1.

Theorem 2 For a graph G with isoperimetric dimension δ > 2 and isoperimetric constant c_{δ} , any function f : V (G) → ℝ satisfies

(∑_{u∼v} |f(u) − f(v)|^{2})^{1/2} ≥ c_{δ} \frac{(δ − 1)^{3/2}}{2δ^{3/2}} min_{m}(∑_{v} |f(v) − m|^{α}d_{v})^{1/α}

where α = \frac{2δ}{δ−2}.

Proof: We follow the notation in Theorem 1 where h(x) = f(x) − m. For a real value σ, we define

β(σ) = ∑_{{u,v}∈C(σ)} |h(u) − h(v)|
γ(σ) = |C(σ)|

Clearly,

∑_{u∼v}(h(u) − h(v))^{2} = ∫ _{0}^{∞}β(σ)dσ + ∫ _{−∞}^{0}β(σ)dσ

We will establish lower bounds for ∫ _{0}^{∞}β(σ)dσ. (The second part can be lower

bounded in a similar way.)

We define values z_{0}, z_{1}, …, z_{m}, by induction as follows:

(1) Set z_{0} = 0.

(2) For i ≥ 1, choose z_{i} such that

∫ _{z_{i}}^{z_{i+1}}β(σ)dσ = (z_{i+1} − z_{i})∫ _{z_{i}}^{z_{i+1}}γ(σ)dσ

Claim:

∑_{z_{i}≤h(x)≤z_{i+1}} d_{x} ≥ c_{δ} ( ∑_{h(x)≥z_{i+1}} d_{x})^{\frac{δ−1}{δ}}

Proof: For a vertex x, we define

h_{i}(x) = \{ \begin{matrix}h(x) & if h(x) ∈ [z_{i}, z_{i+1}] \\ z_{i} & if h(x) ≤ z_{i} \\ z_{i+1} & if h(x) ≥ z_{i+1} \end{matrix}

It follows from the definition that

∫ _{z_{i}}^{z_{i+1}}γ(σ)dσ = ∑_{{x,y}∈E} |h_{i}(x) − h_{i}(y)|

∫ _{z_{i}}^{z_{i+1}}β(σ)dσ = ∑_{{x,y}∈E} |h(x) − h(y)| · |h_{i}(x) − h_{i}(y)|
≥ ∑_{{x,y}∈E}(h_{i}(x) − h_{i}(y))^{2}
≥ ( ∑_{{x,y}∈E} |h_{i}(x) − h_{i}(y)|)^{2}/ ∑_{z_{i}≤h(x)≤z_{i+1}} d_{x}

≥ (∫ _{z_{i}}^{z_{i+1}}γ(σ)dσ)^{2}/ ∑_{z_{i}≤h(x)≤z_{i+1}} d_{x}

Since

∫ _{z_{i}}^{z_{i+1}}β(σ)dσ = (z_{i+1} − z_{i})∫ _{z_{i}}^{z_{i+1}}γ(σ)dσ

we have

|z_{i+1} − z_{i}| ∑_{z_{i}≤h(x)≤z_{i+1}} d_{x} ≥ ∫ _{z_{i}}^{z_{i+1}}γ(σ)dσ
≥ |z_{i+1} − z_{i}| min_{z_{i}≤σ≤z_{i+1}} γ(σ)

Therefore,

∑_{z_{i}≤h(x)≤z_{i+1}} d_{x} ≥ c_{δ} ( ∑_{h(x)≤z_{i+1}} d_{x})^{\frac{δ−1}{δ}}

since

γ(σ) ≥ c_{δ} ( ∑_{h(x)≤z_{i+1}} d_{x})^{\frac{δ−1}{δ}}

To simplify the discussion, we consider a modified function defined on a path …, u′_{1}, u_{0}, u_{1}, …, u_{m} where h(u_{i}) = z_{i} for i ≥ 0 and degree of z_{i} is set to be ∑_{z_{i}≤h(x)≤z_{i+1}} d_{x} (adding loops if necessary). It is easy to see that

∑_{u∼v}(h(u) − h(v))^{2} ≥ ∫ _{0}^{∞}β(σ)dσ

= ∑_{i} ∫ _{z_{i}}^{z_{i+1}}β(σ)dσ

= ∑_{i}(z_{i+1} − z_{i})∫ _{z_{i}}^{z_{i+1}}γ(σ)dσ^{M}

= ∑_{i}(z_{i+1} − z_{i})∫ _{z_{i}}^{z_{i+1}}γ′(σ)dσ

where we define

γ′(σ) = c_{δ} ( ∑_{h(x)≤z_{i+1}} d_{x})^{\frac{δ−1}{δ}}

Let T_{i} = ∑_{j≤i} γ(z_{j+1} − z_{j}) + γ(z_{i})z_{i}

From Cor. 2, we have

T_{i} ≥ c_{δ} \frac{δ − 1}{δ}(∑_{j≥i} z \frac{δ}{δ−1} ; j d(u_{j}))^{\frac{δ−1}{δ}} = c_{δ} \frac{δ − 1}{δ}T′_{i}^{\frac{δ−1}{δ}} .

and

T_{i−1} − T_{i} ≥ (γ′(z_{i−1}) − γ′(z_{i}))z_{i−1}

We use the convention that z_{−i} = 0 if i ≥ 0. We consider

P = ∑_{i≥1}(z_{i} − z_{i−1})^{2}γ′(z_{i})
≥ ∑_{i≥1}(z_{i} − z_{i−1})[(z_{i} − z_{i−1})γ′(z_{i})]
= ∑_{i} z_{i}[(z_{i} − z_{i−1})γ′(z_{i}) − (z_{i+1} − z_{i})γ′(z_{i+1})
= ∑_{i} z_{i}[(z_{i+1} − z_{i})(γ′(z_{i}) − γ′(z_{i+1})) + (z_{i} − z_{i−1} − z_{i+1} + z_{i}))(γ′(z_{i})]
= ∑_{i}(z_{i+1} − z_{i})[z_{i}(γ′(z_{i}) − γ′(z_{i+1})) + ∑_{i}[(z_{i} − z_{i−1}) − (z_{i+1} − z_{i}))]z_{i}γ′(z_{i})
= ∑_{i}(z_{i+1} − z_{i})(T_{i} − T_{i+1}) + ∑_{i}[(z_{i} − z_{i−1})(z_{i}γ′(z_{i}) − z_{i−1}γ′(z_{i−1})
= ∑_{i}(z_{i+1} − z_{i})(T_{i} − T_{i+1}) − ∑_{i}[(z_{i} − z_{i−1})^{2}γ′(z_{i})
≥ ∑_{i}(z_{i+1} − z_{i})(T_{i} − T_{i+1}) − P

Therefore we have

P ≥ \frac{1}{2} ∑_{i}(z_{i+1} − z_{i})(T_{i} − T_{i+1})

≥ \frac{1}{2} ∑_{i} z_{i}[T_{i−1} − T_{i} − (T_{i} − T_{i+1})]

≥ c_{δ} \frac{δ − 1}{2δ} ∑_{i} z_{i} (T′_{i}^{\frac{δ−1}{δ}} [(1 + \frac{z \frac{δ}{δ−1} ; i d(u_{i})}{T′_{i}})^{\frac{δ−1}{δ}} − 1] − (1 − (1 − \frac{z \frac{δ}{δ−1} ; i+1 d(u_{i+1})}{T′_{i}})^{\frac{δ−1}{δ}}))

≥ c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} ∑_{i} z_{i}T′ \frac{δ−1}{δ} ; i \frac{z \frac{δ}{δ−1} ; i d(u_{i}) − z \frac{δ}{δ−1} ; i+1 d(u_{i+1})}{T′_{i}}

≥ c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} ∑_{i} z_{i} \frac{z \frac{δ}{δ−1} ; i d(u_{i}) − z \frac{δ}{δ−1} ; i+1 d(u_{i+1})}{T′_{i}^{1/δ}}  (7)

Now, we substitute for d(u_{i}) and obtain

P ≥ c_{δ}^{2} \frac{(δ − 1)^{2}}{2δ^{2}} ∑_{i} z_{i} \frac{z \frac{δ}{δ−1} ; i (∑_{j≥i} d(u_{j}))^{\frac{δ−1}{δ}} − z \frac{δ}{δ−1} ; i+1 ( ∑_{j≥i+1} d(u_{j}))^{\frac{δ−1}{δ}}}{T′_{i}^{1/δ}}

≥ c_{δ}^{2} \frac{(δ − 1)^{2}}{2δ^{2}} ∑_{i} \frac{z \frac{2δ−1}{δ−1} ; i ( ∑_{j≥i+1} d(u_{j}))^{\frac{δ−1}{δ}} [(1 + \frac{d(u_{i})}{∑_{j≥i+1} d(u_{j})})^{\frac{δ−1}{δ}} − 1 − (z \frac{δ}{δ−1} ; i+1 − z \frac{δ}{δ−1} ; i)]}{T′_{i}^{1/δ}}

≥ c_{δ}^{2} \frac{(δ − 1)^{3}}{2δ^{3}} [∑_{i} \frac{z \frac{2δ−1}{δ−1} ; i d(u_{i})}{( ∑_{j≥i+1} d(u_{j}))^{\frac{1}{δ−1}} T′_{i}^{1/δ}} − ∑_{i} \frac{z_{i}(z \frac{δ}{δ−1} ; i+1 − z \frac{δ}{δ−1} ; i)( ∑_{j≥i+1} d(u_{j}))^{\frac{1}{δ−1}}}{T′_{i}^{1/δ}} ]

≥ c_{δ}^{2} \frac{(δ − 1)^{3}}{2δ^{3}} ∑_{i} \frac{z \frac{2δ−1}{δ−1} ; i d(u_{i})}{( ∑_{j≥i+1} d(u_{j}))^{\frac{1}{δ−1}} T′_{i}^{1/δ}} − P

where the last inequality uses (??). Putting things together, we have

P ≥ c_{δ}^{2} \frac{(δ − 1)^{3}}{4δ^{3}} ∑_{i} \frac{z \frac{2δ}{δ−2} ; i d(u_{i})}{z \frac{2}{δ−2} + \frac{δ}{(δ−1)(δ−2)}_{i} ( ∑_{j≥i+1} d(u_{j}))^{\frac{1}{δ−1}} (∑_{j≥i} z \frac{δ}{δ−1} ; j)^{1/δ}}

≥ c_{δ}^{2} \frac{(δ − 1)^{3}}{4δ^{3}} \frac{∑_{i} z \frac{2δ}{δ−2} ; i d(u_{i})}{(∑_{j≥i} d(u_{j}))^{\frac{2}{δ}}}

≥ c_{δ}^{2} \frac{(δ − 1)^{3}}{4δ^{3}} (∑_{i} z \frac{2δ}{δ−2} ; i d(u_{i}))^{\frac{δ−2}{δ}}

In a similar way we can also lower bound

∫ _{−∞}^{0}β(σ)dσ

Therefore,

(∑_{i∼j}(h(i) − h(j))^{2})^{\frac{1}{2}} ≥ \sqrt{c_{δ}} \frac{(δ − 1)^{3/2}}{2δ^{3/2}} (∑_{i} |h(i)|^{α}d_{i})^{\frac{1}{α}}

since α ≥ 2.

4 The heat kernel of a graph

For a graph G on n vertices, we express its Laplacian

L = ∑_{i=0}^{n−1} λ_{i}P_{i}

where P_{i} is the projection to the ith eigenfunction γ_{i}. The heat kernel K_{t} of G is defined to be the n × n matrix

K_{t} = ∑_{i} e^{−λ_{i}t}P_{i}
= e^{−tL}

In particular,

K_{0} = I.

The heat kernel as defined above is in fact quite a natural thing to consider. It is called the heat kernel since it provides solutions to the temperature distributions at time t when we consider the Riemannian manifold as a homogeneous isotropic medium. In a graph, the heat kernel can be viewed as a continuoustime analogue of a random walk. The reader is referred to [?] and [?] for more background on this topic.

Some useful properties of the heat kernel follow directly from its definition and can be briefly summarized here: Lemma 2: For x, y ∈ V (G), we have

(i)

K_{t}(x, y) = ∑ e^{−tλ_{i}}γ_{i}(x)γ_{i}(y)

where γ_{i} is the eigenfunction corresponding to the eigenvalue λ_{i}.

(ii) For any 0 ≤ a ≤ t,

K_{t}(x, y) = ∑_{z} K_{a}(x, z)K_{t−a}(z, y)

(iii) For f : V (G) → R,

K_{t}f(x) = ∑_{y} K_{t}(x, y)f(y).

(vi) K_{t} satisfies the heat equation

\frac{∂}{∂t}K_{t} = −LK_{t}.

(v)

K_{t}(x, y) ≥ 0.

(vi)

K_{t}S^{−1}1 = S^{−1}1

In particular,

K_{t}(x, x) = ∑_{y}(K_{\frac{t}{2}} (x, y))^{2}

From here, we will deduce a series of inequalities about \frac{∂}{∂t}K_{t} which will eventually lead to a proof of Theorem 3. We first consider

\frac{∂}{∂t}K_{t}(x, x) = 2 ∑_{y} K_{\frac{t}{2}} (x, y)\frac{∂}{∂t}K_{\frac{t}{2}} (x, y)
= ∑_{y} K_{\frac{t}{2}} (x, y) ∑_{i}(−λ_{i})e^{−tλ_{i}/2}γ_{i}(x)γ_{i}(y)
= ∑_{γ} K_{\frac{t}{2}} (x, y)(−LK_{\frac{t}{2}} (y, x))
= − ∑_{γ} K_{\frac{t}{2}} (x, y)SLSK_{\frac{t}{2}} (y, x)
= − ∑_{y} K^{\frac{t}{2}} (x, y) ∑_{z} S(y, y)L(y, z)S(z, z)K_{\frac{t}{2}} (z, x)

= − ∑_{y} K_{\frac{t}{2}} (x, y) ∑_{\begin{matrix}z \\ x∼y \end{matrix}} \frac{1}{\sqrt{d}_{y}} (\frac{1}{\sqrt{d_{y}}} K_{\frac{t}{2}} (y, x) − \frac{1}{\sqrt{d_{z}}} K_{\frac{t}{2}} (z, x))

= − ∑_{y∼z} (\frac{K_{\frac{t}{2}} (y, x)}{\sqrt{d_{y}}} − \frac{K_{\frac{t}{2}} (z, x)}{\sqrt{d_{z}}})^{2}

Now we apply Theorem 1 by considering K_{\frac{t}{2}} (y, x) as a function of y with fixed x. For α = \frac{2δ}{δ−2}, we have

\frac{∂}{∂t}K_{t}(x, x) ≤ −c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} (∑_{y} (\frac{K_{\frac{t}{2}} (y, x)}{\sqrt{d_{y}}} − m)^{α} d_{y})^{2/α}  (8)

To proceed, we need the following fact. Lemma 3:

(∑_{y} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m)^{α} d_{y})^{\frac{1}{α−1}} (3\sqrt{d_{x}})^{\frac{α−2}{α−1}}

≥ ∑_{y} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m)^{2} d_{y}.

Proof: We apply Hőlder’s inequality for 1 = \frac{1}{p} + \frac{1}{q},

∑_{i} f_{i}g_{i} ≤ (∑_{i} f_{i}^{p})^{1/p}(∑_{i} g_{i}^{q})^{1/q}

where we take p = α − 1, q = \frac{α−1}{α−2} and

f_{y} = |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m|^{\frac{α}{α−1}} ,

g_{y} = |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m|^{\frac{α−2}{α−1}}

We then obtain

(∑_{y} |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m|^{α}d_{y})^{\frac{1}{α−1}} (∑_{y} |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m|d_{y})^{\frac{α−2}{α−1}}

≥ ∑_{y} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m)^{2} d_{y}

It remains to bound ∑_{y} |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m|d_{y} from above.

We define m′ by

m′ := \frac{\sqrt{d_{x}}}{vol(G)}

It follows from Lemma 2 (vi) that

∑_{y} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m′) d_{y} = ∑_{y} K_{\frac{t}{2}} (x, y)\sqrt{d_{y}} − m′vol(G)
= (K_{\frac{t}{2}} S^{−1}1) (x) − m′vol(G)
= \sqrt{d_{x}} − m′vol(G)
= 0

From the definition of m and the fact that K ≥ 0, we have m′ ≥ m ≥ 0. Let N_{x}^{+} = \{y : \frac{K_{\frac{t}{2}} (y,x)}{\sqrt{d_{y}}} ≥ m′\} and N_{x}^{−} = \{y : \frac{K_{\frac{t}{2}} (y,x)}{\sqrt{d_{y}}} < m′\}.

Now

∑_{y} |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m′|d_{y} = ∑_{y∈N_{x}^{+}} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m′) d_{y} + ∑_{y∈N_{x}^{−}} (m′ − \frac{K_{\frac{t}{y}} (x, y)}{\sqrt{d_{y}}}) d_{y}
= 2 ∑_{y∈N_{x}^{−}} (m′ − \frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}}) d_{y}
≤ 2 ∑_{y∈N_{x}^{−}} m′d_{y}
= 2\frac{\sqrt{d_{x}}}{vol(G)} · ∑_{y∈N_{x}^{−}} d_{y}
≤ 2\sqrt{d_{x}}

Therefore,

∑_{y} |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m|d_{y} ≤ ∑_{y} |\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m′|d_{y} + ∑_{y} |m′ − m|d_{y}
≤ 2\sqrt{d_{x}} + ∑_{y} m′d_{y}
≤ 3\sqrt{d_{x}}

The proof of Lemma 3 is complete.

We now return to inequality (7). Using Lemma 3 we obtain

\frac{∂}{∂t}K_{t}(x, x)

≤ −c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} (∑_{y} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m)^{α} d_{y})^{2/α}

≤ −c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} (∑_{y} (\frac{K_{\frac{t}{2}} (x, y)}{\sqrt{d_{y}}} − m)^{2} d_{y})^{\frac{2(α−1)}{α}} (3\sqrt{d_{x}})^{\frac{−2(α−2)}{α}}

≤ −c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} (∑_{y}((K_{\frac{t}{2}} (x, y))^{2} − 2mK_{\frac{t}{2}} (x, x)\sqrt{d_{y}} + m^{2}d_{y}))^{\frac{2(α−1)}{α}} (3\sqrt{d_{x}})^{− \frac{2(α−2)}{α}}

≤ −c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} (K_{t}(x, x) − 2mm′\sqrt{d_{x}} + m^{2}vol(G))^{2( \frac{α−1}{α})}(3\sqrt{d_{x}})^{− \frac{2(α−2)}{α}}
≤ −c_{δ} \frac{(δ − 1)^{2}}{2δ^{2}} (K_{t}(x, x) − \frac{d_{x}}{vol(G)})^{2 \frac{(α−1)}{α}} (3\sqrt{d_{x}})^{− \frac{2(α−2)}{α}}

using the fact that m′ ≥ m. We then consider

\frac{∂}{∂t}(K_{t}(x, x) − \frac{d_{x}}{vol(G)})^{1−2 \frac{(α−1)}{α}}

= −\frac{2}{δ}(K_{t}(x, x) − \frac{d_{x}}{vol(G)})^{−2( \frac{α−1}{α})} \frac{∂}{∂t}K_{t}(x, x)
≥ c_{δ} \frac{(δ − 1)^{2}}{δ^{3}} (K_{t}(x, x) − \frac{d_{x}}{vol(G)})^{−2( \frac{α−1}{α})+2( \frac{α−1}{α})}(3\sqrt{d_{x}})^{−2 \frac{(α−2)}{α}}
≥ c_{δ} \frac{(δ − 1)^{2}}{δ^{3}} (3\sqrt{d_{x}})^{−2 \frac{(α−2)}{α}}

using the fact that 1 − 2(\frac{α−1}{α}) = −\frac{2}{δ}. Therefore, we have

(K_{t}(x, x) − \frac{d_{x}}{vol(G)})^{− \frac{2}{δ}} ≥ c_{δ} \frac{(δ − 1)^{2}}{δ^{3}} (3\sqrt{d_{x}})^{−2( \frac{α−2}{α})}t + (1 − \frac{d_{x}}{vol(G)})^{− \frac{2}{δ}}
≥ c_{δ} \frac{(δ − 1)^{2}}{δ^{3}} (3\sqrt{d_{x}})^{−2 \frac{(α−2)}{α}} t

i.e.,

K_{t}(x, x) − \frac{d_{x}}{vol(G)} ≤ \frac{C_{δ}d_{x}}{t^{\frac{δ}{2}}}

where C_{δ} = 9δ^{\frac{3δ}{2}} (c_{δ}^{2}(δ − 1))^{−δ}. Hence,

∑_{x} K_{t}(x, x) − 1 ≤ \frac{C_{δ}vol(G)}{t^{\frac{δ}{2}}}

Since

∑_{x} K_{t}(x, x) = ∑_{x}(∑_{i} e^{−λ_{i}t}γ_{i}^{2}(x)) = ∑_{i} e^{−λ_{i}t},

we have proved the following: Theorem 3

∑_{i≠0} e^{−λ_{i}t} ≤ \frac{C_{δ}vol(G)}{t^{\frac{δ}{2}}}  (9)

where C_{δ} = 9δ^{\frac{3δ}{2}} (c_{δ}^{2}(δ − 1))^{−δ}. From Theorem 3, we derive bounds for eigenvalues. Theorem 4 The k-th eigenvalue λ_{k} of L satisfies

λ_{k} ≥ C′_{δ}(\frac{k}{vol(G)})^{2/δ}

where C′_{δ} = \frac{c_{δ}(δ−1)^{2}}{2eδ^{2}3^{4/δ}}. Proof: From (7) we have

ke^{−λ_{k}t} ≤ \frac{c_{δ}vol(G)}{t^{\frac{δ}{2}}}

The function \frac{e^{λ_{k}t}}{t^{\frac{δ}{2}}} is minimized when t = \frac{δ}{2λ_{k}}. Therefore

k ≤ C_{δ}vol(G) · inf_{t} \frac{e^{λ_{k}t}}{t^{\frac{δ}{2}}}
= C_{δ}vol(G) · (\frac{2λ_{k}e}{δ})^{\frac{δ}{2}}

This implies

λ_{k} ≥ \frac{δ}{2e}(\frac{k}{C_{δ}vol(G)})^{\frac{2}{δ}}
= C′_{δ}(\frac{k}{vol(G)})^{\frac{2}{δ}}
where C′_{δ} = \frac{c_{δ}(δ − 1)^{2}}{2eδ^{2}3^{4/δ}} .

5 Generalization to weighted graphs and irreducible reversible Markov chains

A weighted undirected graph G_{π} with loops allowed has associated with it a weight function π : V × V → ℝ^{+} ∪ {0} satisfying

π(u, v) = π(v, u)

and

π(u, v) = 0 if {u, v} ∉ E(G) .

The definitions and results in previous sections can be easily generalized as follows. We define

1. d_{v}, the degree of a vertex v of G_{π} by d_{v} = ∑_{u} π(v, u)

2. The Laplacian L of G_{π},

L(u, v) = \{ \begin{matrix}1 − \frac{π(v,v)}{d_{v}} & if u = v \\ −\frac{π(u,v)}{\sqrt{d_{u}d_{v}}} & if u ≠ v \end{matrix}

Let λ_{0} = 0 ≤ λ_{1} ≤ ⋯ ≤ λ_{n−1} denote the eigenvalues of L. Then

λ_{1} = min_{f} max_{m} \frac{∑_{u} ∑_{v}(f(u) − f(v))^{2}π(u, v)}{2 ∑_{v} d_{v}(f(v) − m)^{2}}

3. G has isoperimetric dimension δ and isoperimetric constant c_{δ} if

∑_{u∈X} ∑_{v∈X̄} π(u, v) ≥ c_{δ}(vol(X))^{1− \frac{1}{δ}}

for all X ⊆ V (G) with vol(X) ≤ vol(X̄) where vol(X) = ∑_{v∈X} d_{v}.

The results in previous sections can be generalized to the Laplacian of weighted undirected graphs. We will state these facts but omit the proofs which follow the proofs in Sections 3 and 4 in a similar fashion.

Theorem 5 In a weighted undirected graph G_{π} with isoperimetric dimension δ and isoperimetric constant c_{δ} , any function f : V (G) → ℝ satisfies

∑_{u} ∑_{v} |f(u) − f(v)|π(u, v) ≥ c_{δ} \frac{δ − 1}{2δ}min_{m}(∑_{v} |f(v) − m|^{\frac{δ}{δ−1}} d_{v})^{\frac{δ−1}{δ}}

Theorem 6 In a weighted undirected graph G_{π} with isoperimetric dimension δ > 2 and isoperimetric constant c_{δ}, any function f : V (G) → ℝ satisfies

(∑_{u} ∑_{v} |f(u) − f(v)|^{2}π(u, v))^{1/2} ≥ \sqrt{c_{δ}} \frac{δ − 1}{2δ} min_{m}(∑_{v} |f(v) − m|^{α}d_{v})^{1/α}

where α = \frac{2δ}{δ−2}.

Theorem 7 For a weighted undirected graph G, the eigenvalues of its Laplacian L satisfy

∑_{i≠0} e^{−λ_{i}t} ≤ \frac{C_{δ}vol(G)}{t^{δ/2}}

where C_{δ} = 9δ^{\frac{2δ}{2}} (c_{δ}^{2}(δ − 1))^{−δ} and t > 0.

Theorem 8 For a weighted undirected graph G with isoperimetric dimension δ and isoperimetric constant c_{δ}, the k-th eigenvalue of L satisfies

λ_{k} ≥ C′_{δ}(\frac{k}{vol(G)})^{2/δ}

where C′_{δ} = c_{δ} \frac{(δ−1)^{2}}{2eδ^{2}3^{4/8}} .

An irreducible reversible Markov chain can be viewed as a weighted undirected graph G_{π} with the transition probability matrix P satisfying

P (u, v) = \frac{π(u, v)}{∑_{w} π(w, v)}.

Furthermore, the stationary distribution is just _{\frac{d_{v}}{∑_{v} d_{v}}} at the vertex v. We

note that the connectivity of the graph is equivalent to the irreducibility of the Markov chain. The Laplacian L of G_{π} and P have complementary eigenvalues since

P = I − SLS^{−1}

where S is defined as in Section 2. Therefore the statements in Theorems 5-8 apply to irreducible reversible Markov chains as well.

References

[1] N. Alon and V. D. Milman, λ_{1} isoperimetric inequalities for graphs and superconcentrators, J. Comb. Theory B 38 (1985), 73-88.

[2] L. Babai and M. Szegedy, Local expansion of symmetrical graphs, Combinatorics, Probability and Computing 1 (1991), 1-12.

[3] B. Bollobás, Extremal Graph Theory, Academic Press, London (1978).

[4] R. Brooks, The spectral geometry of k-regular graphs, to appear in J. d’Analyse.

[5] P. Buser, Cayley graphs and planar isospectral domains, in Geometry and Analysis on Manifords (T. Sunada ed.), Springer Lecture Notes 1339 (1988) 64-77.

[6] J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis, (R. C. Gunning, ed.) Princeton Univ. Press (1970) 195-199.

[7] Isaac Chavel, Eigenvalues in Riemannian Geometry Academic Press, 1984

[8] F. R. K. Chung, Spectral Graph Theory, Lecture Notes of CBMS Rigonal Conference Series in Mathematics, 1994

[9] F. R. K. Chung, Eigenvalues of graphs and Cheeger inequalities, preprint.

[10] F. R. K. Chung and S. - T. Yau, Harnack inequalities for graphs and subgraphs.

[11] F. R. K. Chung, A. Grigor’yan and S.-T. Yau, Eigenvalues of the Laplace operator on manifolds and graphs, preprint.

[12] Persi Diaconis and Laurent Saloff-Coste, An application of Harnack inequalities to random walks on nilpotent quotients, preprint.

[13] J. Dodziuk and L. Karp, Spectral and function theory for combinatorial Laplacians, Geometry of Random Motion, Contemp. Math 73, AMS Publication (1988), 25-40.

[14] M. Gromov, Groups of polynomial rowth and expanding maps, Publ. Ihes, 53 (1981) 53-78

[15] W. Hebisch and Laurent Saloff-Coste, Gaussian estimates for markov chains and random walks on groups, preprint.

[16] P. Li and S. T. Yau, Estimates of eigenvalues of a compact riemannian manifold, Amer. Math. Soc. Proc. Symp. Pure Math. 36 (1980) 205-240.

[17] A. Lubotsky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-278.

[18] G.A. Margulis, Explicit group theoretic constructions of combinatorial schemes and their applications for the construction of expanders and concentrators, Journal of Problems of Information Transmission (1988) (in Russian).

[19] B. Mohar, Isoperimetric number of graphs, J. of Comb. Theory (B) 47 (1989), 274-291.

[20] G. Polya, On the eigenvalues of vibrating membranes, Proc. London Math. Soc. 11 (1961) 419-433.

[21] Peter Sarnak, Some Applications of Modular Forms, Cambridge University Press (1990)

[22] A.J. Sinclair and M.R. Jerrum, Approximate counting, uniform generation, and rapidly mixing markov chains (to appear in Information and Computation).

[23] N. Th. Varopoulos, Isoperimetric inequalities and Markov chains, J. Funct. Anal.63 (1985), 215-239

[24] S. T. Yau and Richard M. Schoen, Differential Geometry, (1988), Science Publication Co. (in Chinese)