UPPER BOUNDS FOR EIGENVALUES OF THE DISCRETE AND CONTINUOUS LAPLACE OPERATORS

F. R. K. CHUNG, A. GRIGOR’YAN, AND S.-T. YAU

1. Introduction

In this paper, we are concern with upper bounds of eigenvalues of Laplace operator on compact Riemannian manifolds and finite graphs. While on the former the Laplace operator is generated by the Riemannian metric, on the latter it reflects combinatorial structure of a graph. Respectively, eigenvalues have many applications in geometry as well as in combinatorics and in other fields of mathematics.

We develop a universal approach to upper bounds on both continuous and discrete structures based upon certain properties of the corresponding heat kernel. This approach is perhaps much more general than its realization here. Basically, we start with the following entries:

1. an underlying space M with a finite measure μ;

2. a well-defined Laplace operator Δ on functions on M so that Δ is a self-adjoint operator in L^{2}(M, μ) with a discrete spectrum;

3. if M has a boundary, then the boundary condition should be chosen so that it does not disrupt self-adjointness of Δ and is of dissipative nature;

4. a distance function dist(x, y) on M so that |∇dist| ≤ 1 for an appropriate notion of gradient.

Let λ_{i}, i = 0, 1, 2, ⋯ denote the i-th eigenvalue of −Δ so that 0 = λ_{0} ≤ λ_{1} ≤ ⋯ ≤ λ_{i} ≤ · · ·. Then one of our results states that for any pair of disjoint subsets X, Y ⊂ M

λ_{1} ≤ \frac{4}{dist(X, Y)^{2}}(log \frac{2μM}{\sqrt{μXμY}} )^{2}  (1)

We want to emphasize that validity of (1) does not depend on any a priori assumption on M which would restrict its geometry except compactness. A similar inequality holds in general for the difference λ_{i} − λ_{0} for any i ≥ 1.

Let us note that the most non-trivial term in (1) is a logarithm on the right hand side. In fact, the logarithm comes from a Gaussian exponential term which enters normally heat kernel upper bounds. A similar inequality for λ_{i} can be proved involving distances among k disjoint sets by constructing cutoff functions (close to the indicators of the sets X, Y ) and by using them as trial functions in the minimax property of the eigenvalues.

Let M denote now a graph with a combinatorial Laplacian. We will prove the following inequality. For any two vertex subsets X, Y of a graph on n vertices which is not a complete graph, we will relate λ_{1} to the least distance between a vertex in X to a vertex in Y as follows:

Date:

APPEARED IN ADVANCES IN MATHEMATICS, 117 (1996) 165-178

dist(X, Y) ≤ ⌈\begin{matrix}log & \frac{μM}{\sqrt{μXμY}} \\ log & \frac{1}{1−λ} \end{matrix} ⌉  (2)

where λ = λ_{1} if 1 − λ_{1} ≥ λ_{n−1} − 1 and λ = 1 − (λ_{n−1} − λ_{1})/2 otherwise. Note that, in general λ ≥ λ_{1}/2. Here, for example, μX can denote the sum of degrees of vertices of X and dist(X, Y) denotes the length of a shortest path joining a vertex in X and a vertex in Y. This is best possible within a constant factor for expander graphs with degree k and λ = O(1/\sqrt{k}). In general, we have

λ ≤ log \frac{1}{1 − λ} ≤ ⌈\frac{log \frac{μM}{\sqrt{μXμY}}}{dist(X, Y)} ⌉

for any two subsets X, Y of the vertex set of the graph. We note the inequality (2) generalizes an earlier result in [2] (also see [4]):

diamM ≤ ⌈\frac{log(n − 1)}{log \frac{1}{1−λ}}⌉

Special cases of (2) for regular graphs were investigated by Kahale in [7]. For subsets X_{i}, i = 0, 1, ⋯, k, the distance among X_{i} is defined to be the least distance dist(X_{i}, X_{j}) for i ≠ j. We will generalize (2) by relating λ_{k} to the distance among k + 1 subsets of the vertex set. Namely,

min_{i≠j} dist(X_{i}, X_{j}) ≤ max_{i≠j} ⌈\begin{matrix}log & \sqrt{\frac{μX̄_{i} μX̄_{j}}{μX_{i} μX_{j}}} \\ log & \frac{1}{1−λ′_{k}} \end{matrix} ⌉

where λ′_{k} = λ_{k} if 1 − λ_{k} ≥ λ_{n−1} − 1 and λ′_{k} = 1 − (λ_{n−1} − λ_{k})/2, otherwise.

In the next Section we prove our main results for the continuous case of manifolds. The discrete cases for graphs will be considered in Section 2 with similar but different and simpler proofs. A more general setting will be considered in [10].

2. Eigenvalues on manifolds

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}

Δu = \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 and g = det ∥g_{ij}∥ and u is a smooth function on M.

We admit that the manifold M has a boundary ∂M. If this is the case, we introduce a boundary condition

αu + β \frac{∂u}{∂ν} = 0  (3)

where α(x), β(x) are non-negative smooth functions on M such that α(x)+β(x) > 0 for all x ∈ ∂M.

UPPER BOUNDS FOR EIGENVALUES OF THE DISCRETE AND CONTINUOUS LAPLACE OPERATORS ^{1} 3

For example, both Dirichlet and Neumann boundary conditions suit these assumptions. We note that

1. the Laplace operator with the boundary condition (3) is self-adjoint and has a discrete spectrum in L^{2}(M, μ), where μ is the Riemannian measure;

2. the condition (3) implies

u\frac{∂u}{∂ν} ≤ 0

where ν is the outer normal field on ∂M.

Let us introduce also a distance function dist(x, y) on M ×M which may be equal to the geodesic distance, but in general we shall not assume so. 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.

Let us denote by Φ_{i} the eigenfunction corresponding to the i-th eigenvalue λ_{i} and normalized in L^{2}M, μ so that {Φ_{i}} is an orthonormal frame in L^{2}(M, μ).

Theorem 1. Suppose that we have chosen k + 1 disjoint subsets X_{1}, X_{2}, ...X_{k+1} of M such that the distance between any pair of them is at least D > 0. Then for any k > 1

λ_{k} − λ_{0} ≤ \frac{1}{D^{2}} max_{i≠j}(log \frac{4}{∫_{X_{i}} Φ_{0}^{2} ∫_{X_{j}} Φ_{0}^{2}} )^{2}  (4)

We remark that, for example, if either the manifold has no boundary or the Neumann boundary condition has been chosen the first eigenvalue is 0 and the first eigenfunction is the constant

Φ_{0} = \frac{1}{\sqrt{μM}}

An immediate consequence of Theorem 1 is that for any k > 1

λ_{k} ≤ \frac{4}{D^{2}} max_{i≠j}(log \frac{2μM}{\sqrt{μX_{i}μX_{j}}} )^{2}

Proof of Theorem 1: The proof is based upon two fundamental facts about the heat kernel p(x, y, t) being by definition the unique fundamental solution to the heat equation

\frac{∂u}{∂t}u(x, t) − Δu(x, t) = 0

with the boundary condition (3) if the boundary ∂M is non-empty. The first fact is the eigenfunction expansion

p(x, y, t) = ∑_{i=0}^{∞} e^{−λ_{i}t}Φ_{i}(x)Φ_{i}(y)  (5)

and the second is the following universal estimate:

∫_{X} ∫_{Y} p(x, y, t)f(x)g(y)μ(dx)μ(dy) ≤(∫_{X} f^{2} ∫_{Y} g^{2})^{\frac{1}{2}} exp(−\frac{D^{2}}{4t} − λ_{0}t)  (6)

which is true for any functions f, g ∈ L^{2}(M, μ) and for any two disjoint Borel sets X, Y ⊂ M where D = dist(X, Y).

An inequality of type (6) appeared first in the paper by B.Davies [5] and [8] (on page 73). It was improved in [6] by introducing the term −λ_{0}t in the exponent on the right-hand side of (6). The previous papers treated slightly different situations (for example, without a boundary) and this is why we will show at the end of this Section how to prove (6).

Let us explain first the main idea behind the proof of the Theorem 1 in a particular case k = 2. We start with integrating the eigenvalue expansion (5) as follows

I(f, g) ≡ ∫_{X} ∫_{Y} p(x, y, t)f(x)g(y)μ(dx)μ(dy) = ∑_{i=0}^{∞} e^{−λ_{i}t} ∫_{X} fΦ_{i} ∫_{Y} gΦ_{i}  (7)

Let us denote by f_{i} the Fourier coefficients of the function f 1_{X} with respect to the frame {Φ_{i}} and by g_{i} - that of g 1_{Y} . Then

I(f, g) = e^{−λ_{0}t}f_{0}g_{0} + ∑_{i=1}^{∞} e^{−λ_{i}t}f_{i}g_{i} ≥ e^{−λ_{0}t}f_{0}g_{0} − e^{−λ_{1}t}∥f 1_{X}∥_{2} ∥g 1_{Y} ∥_{2}  (8)

where we used the fact that

|∑_{i=1}^{∞} e^{−λ_{i}t}f_{i}g_{i}| ≤ e^{−λ_{1}t}(∑_{i=1}^{∞} f_{i}^{2} ∑_{i=1}^{∞} g_{i}^{2})^{\frac{1}{2}} ≤ e^{−λ_{1}t}∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2}.

By comparing (8) and (6) we get

exp(−(λ_{1} − λ_{0}))∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2} ≥ f_{0}g_{0} − ∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2} exp(−\frac{D^{2}}{4t} ) .  (9)

Let us choose t so that the second term on the right-hand side (9) is equal to one half of the first one (here we take advantage of the Gaussian exponential since it can be made arbitrarily close to 0 by taking t small enough):

t = \frac{D^{2}}{4 log \frac{2∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2}}{f_{0}g_{0}}} .

For this t, we have

exp(−(λ_{1} − λ_{0}))∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2} ≥ \frac{1}{2}f_{0}g_{0}

which implies

λ_{1} − λ_{0} ≤ \frac{1}{t} log \frac{2∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2}}{f_{0}g_{0}}

and after substituting the value of t, we have

λ_{1} − λ_{0} ≤ \frac{4}{D^{2}}(log \frac{2∥f 1_{X}∥_{2}∥g 1_{Y} ∥_{2}}{f_{0}g_{0}} )^{2}

Finally, we choose f = g = Φ_{0} and taking into account that

f_{0} = ∫_{X} fΦ_{0} = ∫_{X} Φ_{0}^{2},

and

∥f 1_{X}∥_{2} =(∫_{X} Φ_{0}^{2})^{\frac{1}{2}} = \sqrt{f_{0}}

and similar identities hold for g we obtain

λ_{1} − λ_{0} ≤ \frac{1}{D^{2}}(log \frac{4}{∫_{X} Φ_{0}^{2} ∫_{Y} Φ_{0}^{2}} )^{2}

Now we turn to the general case k > 2. Let us consider a function f(x) and denote by f_{i}^{j} the i-th Fourier coefficient of the function f 1_{X_{j}} i.e.

f_{i}^{j} = ∫_{X_{j}} fΦ_{i}.

Let us put also in analogy to the case k = 2

I_{lm}(f, f) = ∫_{X_{l}} ∫_{X_{m}} p(x, y, t)f(x)f(y)μ(dx)μ(dy),

then we have the upper bound for I_{lm}(f, f)

I_{lm}(f, f) ≤ ∥f 1_{X_{l}}∥_{2}∥f 1_{X_{m}}∥_{2} exp(−\frac{D^{2}}{4t} − λ_{0}t)  (10)

while we rewrite the lower bound (8) in another way:

I_{lm}(f, f) ≥ e^{−λ_{0}t}f_{0}^{l}f_{0}^{m} + ∑_{i=1}^{k−1} e^{−λ_{i}t}f_{i}^{l}f_{i}^{m} − e^{−λ_{k}t}∥f 1_{X_{l}}∥_{2}∥f 1_{X_{m}}∥_{2}  (11)

Now we want to kill the middle term on the right-hand side (11) by choosing appropriate l and m. To that end, let us consider k + 1 vectors f^{m} = (f_{1}^{m}, f_{2}^{m}, ⋯, f_{k−1}^{m}), m = 1, 2, ⋯, k + 1 in R^{k−1} and let us supply this (k − 1)-dimensional space with a scalar product given by

(v, w) = ∑_{i=0}^{k−2} v_{i}w_{i}e^{−λ_{i+1}t}.

We suppose that we have chosen a value of t from the very beginning so t will not vary (although the optimal value of t will be found later). Let us apply the following elementary fact: out of any k + 1 vectors in (k − 1)-dimensional Euclidean space there are always two vectors with non-negative scalar product (see the end of this section for the proof). Therefore, we can find different l, m so that (f^{l}, f^{m}) ≥ 0 and due to that choice we are able to cancel the second term on the right-hand side (11).

Comparing (10) and (11) we get

e^{−(λ_{k}−λ_{0})t}∥f 1_{X_{l}}∥_{2}∥f 1_{X_{m}}∥_{2} ≤ f_{0}^{l}f_{0}^{m} − ∥f 1_{X_{l}}∥_{2}∥f 1_{X_{m}}∥_{2} exp(−\frac{D^{2}}{4t} )  (12)

Now, similar to the case k = 2 we choose t so that the right-hand side is at least \frac{1}{2}f_{0}^{l}f_{0}^{m}. Since t must be independent on l, m we put simply

t = min_{l≠m} \frac{D^{2}}{4 log \frac{2∥f 1_{X_{l}} ∥_{2}∥f 1_{Xm} ∥_{2}}{f_{0}^{l}f_{0}^{m}}}

and obtain from (12)

λ_{k} − λ_{0} ≤ \frac{1}{t} log \frac{2∥f 1_{X_{l}}∥_{2}∥f 1_{X_{m}}∥_{2}}{f_{0}^{l}f_{0}^{m}}

whence (4) follows by substituting t from above and by taking f = Φ_{0}. □

Now we will prove two auxiliary facts used in the course of the proof of Theorem 1.

Lemma 1. For any two Borel sets X, Y ⊂ M and for any functions f, g ∈ L^{2}(M, μ) we have:

∫_{X} ∫_{Y} p(x, y, t)f(x)g(y)μ(dx)μ(dy) ≤(∫_{X} f^{2} ∫_{Y} g^{2})^{\frac{1}{2}} exp(−\frac{D^{2}}{4t} − λ_{1}t)

where D = dist(X, Y).

Proof of Lemma 1: Let us put

u(x, t) = ∫_{Y} p(x, y, t)g(y)μ(dy)

then u(x, t) is a solution to the heat equation u_{t} = Δu with the initial data u(x, 0) = g 1_{Y} and with the boundary condition (3). As was shown in [6], for any Lipschitz function ξ(x, t) such that for all x ∈ M, t > 0

ξ_{t} + \frac{1}{2}|∇|ξ ≤ 0

the integral

e^{2λ_{0}t} ∫_{M} u^{2}e^{ξ(x,t)}μ(dx)

is a decreasing function of t. Actually, this was proved for the Dirichlet boundary value problem but the proof used only that

u\frac{∂u}{∂ν} ≤ 0

that is true in our setting.

Let us put

ξ(x, t) = \frac{d^{2}(x)}{2(t + ϵ)}

where d(x) ≡ dist(x, Y) and ϵ > 0. Then

e^{2λ_{0}t} ∫_{X} u^{2}(x, t)e^{ξ(x,t)}μ(dx) ≤ ∫_{M} u^{2}(x, 0)e^{ξ(x,0)}μ(dx)

or, taking into account that u(x, 0) = g 1_{Y} , ξ|_{Y} = 0, and ξ|_{X} ≥ \frac{D^{2}}{2(t+ϵ)} and letting ϵ → 0 we get

∫_{X} u^{2}(x, t)μ(dx) ≤ exp(−\frac{D^{2}}{2t} − 2λ_{0}t) ∫_{Y} g^{2}(x)μ(dx).

Finally, we obtain upon an application of the Cauchy-Schwarz inequality

∫_{X} ∫_{Y} p(x, y, t)f(x)g(y)μ(dx)μ(dy) = ∫_{X} u(x, t)f(x)μ(dx)

≤(∫_{X} f^{2})^{\frac{1}{2}}(∫_{X} u^{2}(x, t))^{\frac{1}{2}}

≤(∫_{X} f^{2})^{\frac{1}{2}}(∫_{Y} g^{2})^{\frac{1}{2}} exp(−\frac{D^{2}}{4t} − λ_{0}t)

what was to be proved. □

Now let us prove the next geometric lemma.

Lemma 2. Let E be an n-dimensional Euclidean space and v_{1}, v_{2}, ⋯, v_{n+2} be n+2 arbitrary vectors in E. Then there are two of them, say, v_{i}, v_{j} (where i ≠ j ) such that (v_{i}, v_{j}) ≥ 0 where (·, ·) denotes the scalar product in E.

Proof of Lemma 2: For n = 1 this is obvious. Let us prove the inductive step from n − 1 to n. Suppose that for each pair of the given vectors their scalar product is negative. Let E′ be a hyperplane orthogonal to v_{n+2} and let v_{i}′ be a projection of v_{i} on E′, i = 1, 2, ...n + 1. We claim that (v_{i}′, v_{j}′) < 0 provided i ≠ j. Indeed, since (v_{i}, v_{n+2}) < 0 (where we assume i ≤ n + 1 ) all vectors v_{i} lie on the same half-space with respect to E′ which implies that each of them is represented in the form

v_{i} = v_{i}′ + a_{i}e

where a_{i} > 0 and e is a unit vector orthogonal to E′ and directed to the same half-space as all v_{i}. Hence, we have

0 > (v_{i}, v_{j}) = (v_{i}′ − a_{i}e, v_{j}′ − a_{j}e) = (v_{i}′, v_{j}′) + a_{i}a_{j}

whence (v_{i}′, v_{j}′) < 0 follows. On the other hand, by the induction hypothesis out of n + 1 vectors v_{i}′, i = 1, 2, ...n + 1 in the (n − 1) -dimensional space E′ there are two vectors with non-negative scalar product. This contradiction proves the lemma. □

3. Eigenvalues on graphs

Let G denote a graph on vertex set V (G) and edge set E(G). For a vertex v, the degree of v is denoted by d_{v} and for a subset X of V (G), we define the volume of X to be

μX = ∑_{x∈X} d_{x}

The Laplacian of the graph is defined to be

L(x, y) = \{ \begin{matrix}1 & if x = y; \\ −\frac{1}{\sqrt{d_{x}d_{y}}} & if x ∼ y \\ 0 & otherwise \end{matrix}

Suppose L has eigenvalues λ_{0} = 0 ≤ λ_{1} ≤ ⋯ ≤ λ_{n−1} where n = |V (G)|. Then

λ_{1} = inf_{f} \frac{∑_{x∼y}[f(x) − f(y)]^{2}}{∑_{x} f^{2}(x)d_{x}}

where f ranges over functions satisfying

∑_{x} f(x)d_{x} = 0.

Let T be an n × n function with the (x, x)-entry of value d_{x}. Then T^{1/2}1 is the eigenfunction associated with eigenvalue 0 where 1 denotes the function with all entries 1. It is not difficult to see that λ_{1} ≤ 1 for any graph which is not a complete graph and 1 < λ_{n−1} ≤ 2. More discussions on the eigenvalues λ_{i} can be found in [3]. Let X̄ denote the complement of X in V (G).

8 F. R. K. CHUNG, A. GRIGOR’YAN, AND S.-T. YAU

Theorem 2. Suppose G is not a complete graph. For X, Y ⊂ V (G), we have

dist(X, Y) ≤ ⌈\begin{matrix}log & \sqrt{\frac{μX̄μȲ}{μX μY}} \\ log & \frac{1}{1−λ} \end{matrix} ⌉  (13)

where λ = λ_{1} if 1 − λ_{1} ≥ λ_{n−1} − 1 and λ = 1 − (λ_{n−1} − λ_{1})/2 otherwise. Proof: For X ⊂ V (G), we define

f_{X}(x) = \{ \begin{matrix}1 & if x ∈ X \\ 0 & otherwise \end{matrix}

If we can show that for some integer t and a polynomial p_{t}(z) of degree t,

⟨T^{1/2}f_{Y} , p_{t}(L)(T^{1/2}f_{X})⟩ > 0

then there is a path of length at most t joining a vertex in X to a vertex in Y. Therefore we have dist(X, Y) ≤ t.

Let a_{i} denote the Fourier coefficient of T^{1/2}f_{X}, i.e.,

T^{1/2}f_{X} = ∑_{i=0}^{n−1} a_{i}ϕ_{i}

where ϕ_{i}’s are eigenfunctions of L. In particular, we have

a_{0} = \frac{⟨T^{1/2}f_{X}, T^{1/2}1⟩}{⟨T^{1/2}1, T^{1/2}1⟩}
= \frac{μX}{μV} T^{1/2}1

Similarly, we write

T^{1/2}f_{Y} = ∑_{i=0}^{n−1} b_{i}ϕ_{i}

We choose

p_{t}(z) = \{ \begin{matrix}(1 − z)^{t} & if 1 − λ_{1} ≥ λ_{n−1} − 1 ; \\ (\frac{(λ_{1}+λ_{n−1})}{2} − z)^{t} & otherwise \end{matrix}

Since G is not a complete graph, λ_{1} ≠ λ_{n−1} and |p_{t}(λ_{i})| ≤ (1 − λ)^{t}

UPPER BOUNDS FOR EIGENVALUES OF THE DISCRETE AND CONTINUOUS LAPLACE OPERATORS ^{4} 9

for all i = 1, ⋯, n − 1, therefore we have

⟨T^{1/2}f_{Y} , p_{t}(L)T^{1/2}f_{X}⟩ = a_{0}b_{0} + ∑_{i>0} p_{t}(λ_{i})a_{i}b_{i}
> a_{0}b_{0} − (1 − λ)^{t}\sqrt{∑_{i>0} a_{i}^{2} ∑_{i>0} b_{i}^{2}}
= \frac{μX μY}{μV} − (1 − λ)^{t} \frac{\sqrt{μX μX̄ μY μȲ}}{μV}

Note that

∑_{i>0} a_{i}^{2} = ∥T^{1/2}f_{X}∥^{2} − \frac{(μX)^{2}}{μV}
= \frac{μX μX̄}{μV}

If we choose

t ≥ \begin{matrix}log & \sqrt{\frac{μ X̄ μȲ}{μX μY}} \\ log & \frac{1}{1−λ} \end{matrix}

we have

⟨T^{1/2}f_{Y} , p_{t}(L)T^{1/2}f_{X}⟩ > 0

Therefore we have

dist(X, Y) ≤ t. □

To improve the inequality in some cases, we use the same approach as in [4] by considering the Chebychev polynomials of the first kind.

T_{0}(z) = 1,
T_{1}(z) = z,
T_{t+1}(z) = 2zT_{t}(z) − T_{t−1}(z), for integer t > 1.

Or, equivalently,

T_{t}(z) = cosh(t cosh^{−1}(z)).

In the place of p_{t}(L), we will use S_{t}(L) where

S_{t}(x) = \frac{T_{t}(\frac{λ_{1}+λ_{n−1}−2x}{λ_{n−1}−λ_{1}})}{T_{t}(\frac{λ_{n−1}+λ_{1}}{λ_{n−1}−λ_{1}} )}

Then we have

max_{x∈[λ_{1},λ_{n−1}]} ≥ S_{t}(λ_{1}) ≥ \frac{1}{T_{t}(\frac{λ_{n−1}+λ_{1}}{λ_{n−1}−λ_{1}} )}

Suppose we take

t ≥ cosh^{−1} \sqrt{\frac{μ X̄ μȲ}{μX μY}} ; cosh^{−1} \frac{λ_{n−1}+λ_{1}}{λ_{n−1}−λ_{1}}

Then we have

⟨T^{1/2}f_{Y} , S_{t}(L)T^{1/2}f_{X}⟩ > 0

Theorem 3. Suppose G is not a complete graph. For X, Y ⊂ V (G), we have

dist(X, Y) ≤ ⌈\begin{matrix}cosh & −1 & \sqrt{\frac{μX̄μȲ}{μX μY}} \\ cosh & −1 & \frac{λ_{n−1}+λ_{1}}{λ_{n−1}−λ_{1}} \end{matrix} ⌉

We can easily derive isoperimetric inequalities by using (13). These isoperimetric inequalities are generalizations of the inqualities concerning vertex or edge “expansion” in Tanner [9] and in Alon and Miller [1] for regular graphs.

For a subset X ⊂ V, we define the s-neighborhood of X by

N_{s}(X) = {y : dist(x, y) ≤ s, for some x ∈ X}

Suppose we choose Y = V − N_{s}(X) in (13). Theorem 2 implies the following result which gives a lower bound for the expansion of the neighborhood.

μN_{t}(X) ≥ \frac{μX}{\frac{μX}{μV} + (1 − \frac{μX}{μV})(1 − λ)^{2t}}

Theorem 2 can be generalized for the case of relating the distance of k + 1 disjoint subsets of vertices and the eigenvalues λ_{k}. The line of proof is quite similar to that in Section 2.

Theorem 4. Suppose G is not a complete graph. For X_{i} ⊂ V (G), i = 0, 1, ⋯, k, we have

min_{i≠j} dist(X_{i}, X_{j}) ≤ max_{i≠j} ⌈\begin{matrix}log & \sqrt{\frac{μX̄_{i} μX̄_{j}}{μX_{i} μX_{j}}} \\ log & \frac{1}{1−λ′_{k}} \end{matrix} ⌉

where λ′_{k} = λ_{k} if 1 − λ_{k} ≥ λ_{n−1} − 1 and λ′_{k} = 1 − (λ_{n−1} − λ_{k})/2 otherwise.

Proof:

There exist two distinct subsets in X_{i}’s, denoted by X and Y, satisfying

⟨T^{1/2}f_{Y} , p_{t}(L)T^{1/2}f_{X}⟩ ≥ a_{0}b_{0} + ∑_{i=1}^{k−1} p_{t}(λ_{i})a_{i}b_{i} + ∑_{i≥k} p_{t}(λ_{i})a_{i}b_{i}

> \frac{μX μY}{μV} − (1 − λ′_{k})^{t} \frac{\sqrt{μX μX̄ μY μȲ}}{μV}

by using Lemma 2 and by associating to each X a vector (p_{t}(λ_{1})^{1/2}a_{1}, ⋯, p_{t}(λ_{k−1})^{1/2}a_{k−1}) where f_{X} = ∑ a_{i}ϕ_{i}.

References

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

[2] F. R. K. Chung, Diameters and eigenvalues, J. of AMS 2 (1989),187-196.

[3] F. R. K. Chung, Spectral Graph Theory, CBMS Lecture Notes, AMS publication, 1995.

[4] F. R. K. Chung, V. Faber and Thomas A. Manteuffel, On the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. of Discrete Math. 7 (1994),443-457.

[5] E. B. Davies, Heat kernel bounds, conservation of probability and the Feller property, J. d’Analyse Math. 58, (1992), 99-119.

[6] A. Grigor’yan, Integral maximum principle and its applications, Proc. of Edinburgh Royal Society, 124A (1994) 353-362.

[7] Nabile Kahale, Isoperimetric inequalities and eigenvalues, preprint

[8] Peter Li and S. T. Yau, On the parabolic kernel of the Schrödinger operator, Acta Mathematica 156, (1986) 153-201

[9] R.M. Tanner, Explicit construction of concentrators from generalized N-gons, SIAM J. Algebraic Discrete Methods 5 (1984) 287-294.

[10] F. R. K. Chung, A. Grigor’yan and S.-T. Yau, Eigenvalues and diameters for manifolds and graphs, preprint.

University of Pennsylvania, Philadelphia, Pennsylvania 19104

Imperial College, London, SW7 2B2 UK

Harvard University, Cambridge, Massachusetts 02138