Eigenvalues and diameters for manifolds and graphs

F.R.K. Chung * University of Pennsylvania, Philadelphia, Pennsylvania 19104 chung@math.upenn.edu

A. Grigor’yan^{†} Imperial College, London SW7 2BZ, United Kingdom a.grigoryan@ic.ac.uk

S.-T. Yau^{∗}

Harvard University, Cambridge, Massachusetts 02138 yau@math.harvard.edu

0. Introduction

In this paper, we develop a universal approach for estimating from above the eigenvalues of the Laplace operator on the underlying spaces of different kinds: on compact or finite volume Riemannian manifolds (a continuous space) and on finite graphs (a discrete space).

Let first M be a Riemannian manifold equipped with a measure μ = σ(x)μ_{0} where μ_{0} is a Riemannian measure, σ is a positive smooth density. Let us consider an operator

L = −σ^{−1}div(σ∇)  (0.1)

which is self-adjoint in L^{2}(M, μ) (with a proper domain). Obviously, if σ = 1 then L = −Δ with Δ being a Laplace operator of the Riemannian metric.

If M is compact then L has a discrete spectrum in L^{2}(M, μ). Let us denote its eigenvalues by 0 = λ_{0} < λ_{1} ≤ λ_{2} ≤ ... . Our result says in this setting that for any k + 1 disjoint measurable subsets X_{0}, X_{1}, ..., X_{k} ⊂ M

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

where D = min_{i≠j} dist(X_{i}, X_{j}), and dist denotes the Riemannian distance.

In particular, we have for any disjoint sets X, Y

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

† This author is supported by the EPSRC, UK.

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

Chung F.R.K., Grigor’yan A., Yau S.-T., Eigenvalues and diameters for manifolds and graphs, “Tsing Hua Lectures on Geometry and Analysis”, ed. S.-T.Yau, International Press, p.79-105. 1997.

Now let G be a connected graph with a vertex set M and with an edge set E equipped with a conductance c(ξ) > 0, ξ ∈ E. We define a weighted Laplace operator as

Lf(x) = f(x) − ∑_{y∼x} f(y)\frac{c(\overline{xy})}{μ(x)}

where μ(x) = ∑_{y∼x} c(\overline{xy}) is a measure of the point x. The operator L is self-adjoint and non-negative in L^{2}(M, μ). Let us denote its eigenvalues by 0 = λ_{0} < λ_{1} ≤ λ_{2} ≤ ... ≤ λ_{N} where N + 1 is the number of vertices in M.

Our results says that for any k + 1 ≤ N + 1 disjoint non-empty sets X_{0}, X_{1}, , , , X_{k}

min_{i≠j} dist(X_{i}, X_{j}) ≤ max_{i≠j}⌈\begin{matrix}log & \frac{μM}{\sqrt{μX_{i}μX_{j}}} \\ log & \frac{λ_{N} +λ_{k}}{λ_{N} −λ_{k}} \end{matrix} ⌉.  (0.4)

This inequality contains implicitly an upper bound for λ_{k} - see Section 4 for details. For the case k = 2, we rewrite (0.4) as follows

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

Particular cases of the inequality (0.2) for a Laplace-Beltrami operator on a Riemannian manifold and of the inequality (0.5) for a combinatorial Laplace operator on a graph were considered in a paper of the authors [9] . In the present paper, we introduce another method of proving the above inequalities which

• yields numerically better results;

• is applicable to a wider class of operators;

• treats both continuous and discrete case in the same way.

The main idea of the method generalizes that of [6] and can be referred to as a finite propagation speed of a Laplace operator on a graph. Indeed, if u is a function on a graph, then Δu has a support in 1-neighbourhood of suppu. Moreover, if P (z) is a polynomial of the degree s then the support of P (−Δ)u is located in the s−neighbourhood of suppu.

A similar property holds for the Laplace operator on a manifold: the support of the function cos s\sqrt{−Δ}u lies in the s−neighbourhood of suppu. This property was used in [3] to obtain estimates of certain functions of the Laplace operator and to reprove the heat kernel upper bounds of [5] .

In the next two section we introduce the necessary notions and prove the basic facts for an abstract setting. In section 3 we prove eigenvalue estimates for manifolds, and in section 4 we treat the discrete case of graphs.

1. Preliminary definitions and facts

Since we are going to treat both continuous and discrete cases in the same way, we shall introduce a general setting which covers both situations and, perhaps, many others. Let M denote a metric space equipped with a Borel measure μ. Let we be given a self-adjoint (unbounded) operator L in L^{2}(M, μ) with a dense domain which will be a prototype of −Δ. We assume that the following usual properties of Laplacian on compact spaces are true: 1^{∘} the operator L is self-adjoint and non-negative i.e. specL ∈ [0, ∞) 2^{∘} a constant is in DomL (in particular, 1 ∈ L^{2}(M, μ) and the volume μM is finite) and

is an eigenfunction with an eigenvalue 0 i.e.

L1 = 0

In order to make L a real Laplace operator we have to postulate its properties which would make connection to geometry of the space M, namely, to the distance function. Let us introduce the following notation for a neighbourhood of a support of a function:

supp_{r}u = {x ∈ M : dist(x, suppu) ≤ r}

where dist denotes the distance function in M.

We shall assume existence of a finite propagation speed function family P_{s}(λ), namely: 3^{∘} there exists a non-trivial family of bounded continuous functions P_{s}(λ) defined on the

spectrum specL where s runs over [0, +∞) so that for any function u ∈ L^{2}(M, μ)

suppP_{s}(L)u ⊂ supp_{s}u.

Let us consider examples when the hypotheses 1^{∘}-3^{∘} hold.

1. Let M be a complete Riemannian manifold and let L be the unique self-adjoint extension of the operator −Δ where Δ is the Laplace operator associated with the Riemannian metric and acting on the domain C_{c}^{∞}(M) (see [11] , [19] ). As well known, the condition 1^{∘} is true always. The condition 2^{∘} is fulfilled whenever 1 ∈ L^{2}(M, μ) that is, the volume of M is finite (if this is the case then 1 ∈ DomL automatically).

As for 3^{∘}, we can always take P_{s}(λ) = cos s\sqrt{λ}. The finite propagation speed of this family is nothing other than the finite propagation speed of the wave equation (see [18] ).

2. Let M be a compact Riemannian manifold with a boundary or a compact region on another manifold. Let L be a self-adjoint extension of −Δ subject to the Neumann boundary condition. Then all our hypotheses 1^{∘}-3^{∘} do hold with the same family P_{s}(λ) as above.

3. Let M be a complete Riemannian manifold not necessarily with finite volume. Let us denote by μ_{0} a Riemannian volume, take a smooth positive function σ ∈ L^{1}(M, μ_{0}), and introduce another measure μ = σμ_{0} so that the new volume μM is finite. Let us take

L = −Δ − ∇ log σ∇ = −σ^{−1}div(σ∇)

initially with the domain C_{c}^{∞}(M). This operator is symmetric against the measure μ and is uniquely extended to a self-adjoint operator - see [10] for details. It is not difficult to show that all our hypotheses 1^{∘}-3^{∘} are true moreover, with the same family P_{s} as above. Let us emphasize that the distance function under consideration is the Riemannian distance regardless of what function σ is chosen.

4. Let M be a vertex set of a finite connected graph and let L be a (positively defined) combinatorial Laplace operator acting on functions on M. In this case, it is a finite dimensional operator, and the hypotheses 1^{∘}-2^{∘} are fulfilled automatically. The condition 3^{∘} holds if P_{s}(λ) is any polynomial of the degree ⌊s⌋ (where ⌊s⌋ is the floor function i.e. the the greatest integer which does not exceed s) which follows from the obvious fact that suppΔu ∈ supp_{1}u.

Before going any further let us show that the hypotheses 1^{∘}-3^{∘} can be relaxed in the following way. Suppose, that we have a Borel measure μ̂ on M and a self-adjoint operator L̂ in L^{2}(M, μ̂) satisfying instead of 1^{∘}-3^{∘} the following hypotheses: ˆ1^{∘} the spectrum of L̂ lies in the interval [λ_{0}, +∞); ˆ2^{∘} there is a positive L^{2}−function ψ on M which lies in DomL̂ and which is eigenfunction

of L̂ to the eigenvalue λ_{0} i.e. L̂ψ = λ_{0}ψ; ˆ3^{∘} similar to 3^{∘}: for any u ∈ L^{2}(M, μ̂)

suppP_{s}(L̂)u ⊂ supp_{s}u

which coincide with 1^{∘}-3^{∘} provided ψ = 1, λ_{0} = 0, and L̂ = L. Let us show that by an appropriate change of the operator and the measure (but not touching the distance) the general case ˆ1^{∘}-ˆ3^{∘} is reduced to the special case 1^{∘}-3^{∘} as well. To that end, let us introduce another measure μ = ψ^{2}μ̂ and another operator L so that

L = ψ^{−1} ∘ L̂ ∘ ψ − λ_{0}

and DomL = ψ^{−1}DomL̂.

We claim that 1^{∘}-3^{∘} hold for the operator L in the space L^{2}(M, μ). Indeed, 1^{∘} follows from the well-known general fact that the spectra of L̂ in L^{2}(M, μ̂) and of ψ^{−1} ∘ L̂ ∘ ψ in L^{2}(M, ψ^{2}μ̂) coincide. In particular, it yields also that

spec(L, L^{2}(M, μ)) = spec(L̂, L^{2}(M, μ̂)) − λ_{0}

which enables us to transfer any information about the spectrum of L to that of L̂.

The condition 2^{∘} follows from ψ ∈ DomL̂ and L̂ψ = λ_{0}ψ. The condition 3^{∘} follows from suppλ_{0}u ⊂ suppu and

suppP_{s}(ψ^{−1} ∘ L̂ ∘ ψ)u = suppψ^{−1}P_{s}(L̂)(ψu) ⊂ supp_{s}(ψu) ⊂ supp_{s}u.

Let us consider an example when ˆ1^{∘}-ˆ3^{∘} do hold.

5. Let M be a Riemannian manifold (not necessarily complete) and let us denote by μ̂ its Riemannian measure. Let L̂ be a minimal self-adjoint extension of −Δ which can be associated to the Dirichlet boundary condition at the infinity of M (on a noncomplete manifold there may exist different self-adjoint versions of the Laplace operator). For example, if M is a bounded region in IR^{n} or in any other complete Riemannian manifold then L̂ is a self-adjoint operator of the Dirichlet boundary value problem in M.

Suppose that L̂ has a positive L^{2}−eigenfunction ψ i.e.

L̂ψ = λ_{0}ψ

for some number λ_{0}. Then the conditions ˆ2^{∘}-ˆ3^{∘} are obviously true, so is ˆ1^{∘} although the latter is not altogether trivial and we refer to [16] for that.

A typical situation matching this description is a Dirichlet boundary value problem in a bounded region where λ_{0} is its first eigenvalue and ψ is the corrsponding eigenfunction which is automatically positive and in L^{2}.

6. Let q(x) be a smooth function on a complete Riemannian manifold and let L̂ be the minimal self-adjoint extension of the operator −Δ + q(x) acting on smooth compactly supported functions. Let the equation L̂ψ = 0 has a positive L^{2}−solution on M. This situation fits ˆ1^{∘}-ˆ3^{∘} if q(x) is positive. But it can be reduced to 1^{∘}-3^{∘} for a signed q(x) as well. Indeed, if μ̂ is the Riemannian measure then we introduce the measure μ = ψ^{2}μ̂ and the operator L = ψ^{−1} ∘ L̂ ∘ ψ which coincides with L = −\frac{1}{\sqrt{ψ}} div(\sqrt{ψ}∇) (which

follows from L̂ψ = 0) i.e. with the operator from the example 3. Since the spectra spec(L̂, L^{2}(M, μ̂)) = spec(L, L^{2}(M, μ)) then any information about the spectrum of L is carried over to that of L̂.

We conclude this section with a general inequality which will be used in the next sections and which goes back to [3] . In what follows we assume that 1^{∘}-3^{∘} do hold.

Let us put

p(s) = sup_{λ∈specL} |P_{s}(λ)|

and assume that p(s) is a reasonably nice function of s, for example, locally integrable.

We shall consider a linear combination of the functions P_{s} with respect to the parameter s. More precisely, let us put

Φ(λ) = ∫_{0}^{∞} φ(s)P_{s}(λ)ds

where φ(s) be a measurable function on (0, +∞) such that

∫_{0}^{∞} |φ(s)| p(s)ds < ∞.

In particular, Φ(λ) is a bounded function on specL, and we shall be able to apply the operator Φ(L) to any function from L^{2}(M, μ).

Lemma 1.1 If u ∈ L^{2}(M, μ) then

∥Φ(L)u∥_{L^{2}(M\supp_{r}u)} ≤ ∥u∥_{2} ∫_{r}^{∞} |φ(s)| p(s)ds

where ∥u∥_{2} ≡ ∥u∥_{L^{2}(M,μ)} .

Proof of the lemma. Indeed, let us denote

w(x) = Φ(L)u(x) = ∫_{0}^{∞} φ(s)P_{s}(L)u(x)ds.

If the point x is off supp_{r}u then P_{s}(L)u(x) = 0 whenever s ≤ r. Therefore, for those points

w(x) = ∫_{r}^{∞} φ(s)P_{s}(L)u(x)ds

and

∥w∥_{L^{2}(M\supp_{r}u)} ≤ ∥∫_{r}^{∞} φ(s)P_{s}(L)u(x)ds∥_{2}

≤ ∫_{r}^{∞} ∥φ(s)P_{s}(L)u(x)∥_{2} ds ≤ ∫_{r}^{∞} |φ(s)| p(s) ∥u∥_{2} ds

which was to be proved. ⊓ ⊔ Corollary 1.1 If u, v ∈ L^{2}(M, μ) and the distance between the supports of u and v is D then

|∫_{M} vΦ(L)udμ| ≤ ∥u∥_{2} ∥v∥_{2} ∫_{D}^{∞} |φ(s)| p(s)ds  (1.1)

Indeed, the integral on the left hand side of (1.1) is reduced to one over the support of v which in turn is majorized by the integral over the exterior of supp_{D}u. The rest follows by a straightforward application of the Cauchy-Schwarz inequality.

2. The abstract eigenvalue estimates

Throughout this section we assume that the hypotheses 1^{∘}-3^{∘} are true.

Let us denote by spec_{1} the spectrum of L in the subspace of L^{2}(M, μ) orthogonal to constants and put λ_{1} = inf spec_{1}. The purpose of this section is to develop a rather general approach to estimate λ_{1} from above. The heart of the matter is the following statement which reduces the question to playing with the functions of a single variable.

Given a function u ∈ L^{2}(M, μ) we denote by u^{(1)} its component orthogonal to a constant function and by ū − its projection onto the space of constants. In other words,

ū = \frac{1}{μM} ∫_{M} udμ

u^{(1)} = u − ū.

Proposition 2.1 Let u, v be two functions in L^{2}(M, μ) with disjoint supports so that the distance between their supports is equal to D. Then

sup_{λ∈spec_{1}} |Φ(λ)| ≥ Φ(0)\frac{ūv̄μM}{∥u^{(1)}∥_{2}∥v^{(1)}∥_{2}} − \frac{∥u∥_{2}∥v∥_{2}}{∥u^{(1)}∥_{2}∥v^{(1)}∥_{2}} ∫_{D}^{∞} |φ(s)| p(s)ds  (2.1)

provided ∥u^{(1)}∥_{2} > 0, ∥v^{(1)}∥_{2} > 0.

Remark. This inequality contains implicitly an upper bound for λ_{1}. Indeed, let us suppose that the function Φ(λ) is a decreasing one and Φ(0) = 1. Then the left hand side of (2.1) is equal to |Φ(λ_{1})| , and (2.1) implies an upper bound for λ_{1}. Of course, to make it more explicit, one should have chosen all the functions u, v, P_{s}(λ), φ(s). We shall do that in the next sections. Proof. Indeed, we have

Φ(L)u = Φ(L)u^{(1)} + Φ(L)ū

The last term here is equal to Φ(0)ū since the space of constants is an eigenspace of the operator L with the eigenvalue 0. Taking the inner product with the function v = v^{(1)} + v̄ and using the fact that the operator L and any function of it are invariant both in the space of constants and in its orthogonal complement, we have

∫_{M} Φ(L)uvdμ = ∫_{M} Φ(L)u^{(1)}v^{(1)}dμ + Φ(0)ūv̄μM  (2.2)

Since u^{(1)}, v^{(1)} lie in the subspace of L^{2}(M, μ) orthogonal to constants, we have

|∫_{M} Φ(L)u^{(1)}v^{(1)}dμ| ≤ sup_{λ∈spec_{1}} |Φ(λ)| ∥u^{(1)}∥_{2}∥v^{(1)}∥_{2}  (2.3)

and get from (2.2)

∫_{M} Φ(L)uvdμ ≥ Φ(0)ūv̄μM − sup_{λ∈spec_{1}} |Φ(λ)| ∥u^{(1)}∥_{2}∥v^{(1)}∥_{2}.

Combining with the upper bound (1.1) , we shall obtain (2.1) . ⊓ ⊔

Corollary 2.1 Let X, Y be two disjoint subsets of M of a positive measure and let the distance between them be equal to D > 0. Then

sup_{λ∈spec_{1}} |Φ(λ)| ≥ Φ(0)\begin{matrix}√ & \overline{μXμY} \\ √ & \overline{μ\overline{X}μ\overline{Y}} \end{matrix} − \frac{μM}{\sqrt{μ\overline{X}μ\overline{Y}}} ∫_{D}^{∞} |φ(s)| p(s)ds  (2.4)

where \overline{X} = M \ X, \overline{Y} = M \ Y.

Indeed, by taking u = 1_{X}, v = 1_{Y} and by noticing that

∥u∥_{2}^{2} = μX, ū = \frac{μX}{μM} , ∥u^{(1)}∥_{2}^{2} = μX − ū^{2}μM = \frac{μXμ\overline{X}}{μM}

we obtain (2.4) from (2.1) .

Now we turn to the higher eigenvalues. To that end, we have to assume that the spectrum of L consists of a discrete part λ_{0} = 0 ≤ λ_{1} ≤ λ_{2}, ... ≤ λ_{k−1} (where k > 1) and of the rest which lies in the interval [λ_{k−1}, +∞). Let the corresponding eigenfunctions be w_{0} = const, w_{1}, w_{2}, ...w_{k−1} so that they form an orthonormal set in L^{2}(M, μ). Let us denote by spec_{k} the spectrum of L in the subspace of L^{2}(M, μ) which is orthogonal to all w_{0}, w_{1}, ...w_{k−1} and put λ_{k} = inf spec_{k}. By the hypothesis above, λ_{k} ≥ λ_{k−1}.

Given a function u ∈ L^{2}(M, μ) we denote by u^{(k)} the orthogonal projection of u onto the subspace of L^{2}(M, μ) orthogonal to w_{0}, w_{1}, ...w_{k−1}. We denote by Φ, φ, p the same functions as above. For any two functions u, v ∈ L^{2}(M, μ) and D > 0 we introduce the notation

Γ_{k,D}(u, v) = Φ(0)\frac{ūv̄μM}{∥u^{(k)}∥_{2}∥v^{(k)}∥_{2}} − \frac{∥u∥_{2}∥v∥_{2}}{∥u^{(k)}∥_{2}∥v^{(k)}∥_{2}} ∫_{D}^{∞} |φ(s)| p(s)ds

provided the norms ∥u^{(k)}∥_{2}, ∥v^{(k)}∥_{2} are non-vanishing (otherwise, take Γ_{k,D}(u, v) = 0). Proposition 2.1 can be stated in this notation as follows

sup_{λ∈spec_{1}} |Φ(λ)| ≥ Γ_{1,D}(u, v)

whenever the distance between the supports of u, v is at least D.

Proposition 2.2 Let k ≥ 2 and let u_{0}, u_{1}, ...u_{k} be k + 1 functions in L^{2}(M, μ) with disjoint supports. Let us denote by D be the smallest distance between the pairs of their supports. Suppose that the function Φ(λ) is non-negative at the points λ = λ_{1}, λ_{2}, ...λ_{k−1}. Then we have

sup_{λ∈spec_{k}} |Φ(λ)| ≥ inf_{i≠j} Γ_{k,D}(u_{i}, u_{j}).  (2.5)

Remark. The relation (2.5) contains implicitly an upper bound for λ_{k} in the same way as (2.1) is an upper bound for λ_{1}. Also, let us note that Γ_{k,D} can be replaced in (2.5) by a more computable Γ_{1,D} because ∥u^{(k)}∥_{2} ≥ ∥u^{(1)}∥_{2} Proof of Proposition 2.2. Let us pick any two functions out of {u_{i}} and denote them by u, v. We have the following expansions:

u = ū + a_{1}w_{1} + a_{2}w_{2} + ...a_{k−1}w_{k−1} + u^{(k)}  (2.6)
v = v̄ + b_{1}w_{1} + b_{2}w_{2} + ...b_{k−1}w_{k−1} + v^{(k)}

with some coefficients a_{i}, b_{i}. Let us apply the operator Φ(L) to the first expansion and take the inner product with the second one:

∫_{M} Φ(L)uvdμ = Φ(0)ūv̄μM + ∑_{i=1}^{k−1} a_{i}b_{i}Φ(λ_{i}) + ∫_{M} Φ(L)u^{(k)}v^{(k)}dμ.

The integral on the right hand side admits the estimate

|∫_{M} Φ(L)u^{(k)}v^{(k)}dμ| ≤ sup_{λ∈spec_{k}} |Φ(λ)| ∥u^{(k)}∥_{2}∥v^{(k)}∥_{2}

while the integral on the left hand side is estimated via (1.1) . We obtain thus

sup_{λ∈spec_{k}} |Φ(λ)| ∥u^{(k)}∥_{2}∥v^{(k)}∥_{2} ≥ Φ(0)ūv̄μM + ∑_{i=1}^{k−1} Φ(λ_{i})a_{i}b_{i}

− ∥u∥_{2}∥v∥_{2} ∫_{D}^{∞} |φ(s)| p(s)ds.

(2.7)

Now we want to kill the second term on the right hand side (2.7) . We shall be able to do that by a proper choice of the functions u, v. Indeed, for any function u ∈ L^{2}(M, μ) there corresponds a vector a⃗ = (a_{1}, a_{2}, ...a_{k−1}) ∈ IR^{k−1} defined as in (2.6) . For any two vectors a⃗, b⃗ ∈ IR^{k−1} let us introduce their inner product in IR^{k−1} by the rule

(a⃗, b⃗) ≡ ∑_{i=1}^{k−1} Φ(λ_{i})a_{i}b_{i}  (2.8)

Strictly speaking, (2.8) may define a degenerated inner product if Φ(λ_{i}) vanishes at some i = 1, 2, ...k − 1. If this is the case, we can disregard all i’s for which Φ(λ_{i}) = 0, and work in a less dimensional space which is even better for the proof.

Now we apply the following elementary geometric fact: out of any k + 1 vectors in (k − 1)−dimensional Euclidean space, there are always two vectors with non-negative inner product (see [9] for the proof). Therefore, we can choose two functions u, v out of u_{0}, u_{1}, ...u_{k} so that the corresponding sum

∑_{i=1}^{k−1} Φ(λ_{i})a_{i}b_{i}

is non-negative, and we obtain from (2.7) for those functions u, v

sup_{λ∈spec_{k}} |Φ(λ)| ∥u^{(k)}∥_{2}∥v^{(k)}∥_{2} ≥ Φ(0)ūv̄μM − ∥u∥_{2}∥v∥_{2} ∫_{D}^{∞} |φ(s)| p(s)ds.

whence (2.5) follows. ⊓ ⊔

Corollary 2.2 Let we have k+1 disjoint measurable subsets X_{0}, X_{1}, ...X_{k} ⊂ M of positive measure and let the distance between any pair of them be at least D > 0. Then

sup_{λ∈spec_{k}} |Φ(λ)| ≥ inf_{i≠j} \{Φ(0)\begin{matrix}√ & \overline{μX_{i}μX_{j}} \\ √ & \overline{μ\overline{X}_{i}μ\overline{X}_{j}} \end{matrix} − \frac{μM}{\sqrt{μ\overline{X}_{i}μ\overline{X}_{j}}} ∫_{D}^{∞} |φ(s)| p(s)ds\}  (2.9)

provided the function Φ(λ) is non-negative at the points λ_{1}, λ_{2}, ...λ_{k−1}.

Proof follows the same line as that of Corollary 2.1.

Let us now assume that instead of 1^{∘}-3^{∘} we have ˆ1^{∘}-ˆ3^{∘}. The following statement is a straightforward translation of the previous result to that situation. We suppose that φ(s) is a measurable function on (λ_{0}, ∞) such that

∫_{λ_{0}}^{∞} |φ(s)| p(s)ds < ∞

and

Φ(λ) ≡ ∫_{λ_{0}}^{∞} φ(s)P_{s}(λ)ds.

Also, along with the native Riemannian measure μ̂ let us consider another measure μ = ψ^{2}μ̂ where ψ is the eigenfunction to the eigenvalue λ_{0} from the hypotheses ˆ1^{∘}-ˆ3^{∘}.

Corollary 2.3 Let we have k + 1 (k ≥ 1) disjoint measurable subsets X_{0}, X_{1}, ...X_{k} ⊂ M of positive measure and let the distance between any pair of them be at least D > 0. Then

sup_{λ∈spec_{k}(L̂)} |Φ(λ)| ≥ inf_{i≠j} \{Φ(λ_{0})\begin{matrix}√ & \overline{μX_{i}μX_{j}} \\ √ & \overline{μ\overline{X}_{i}μ\overline{X}_{j}} \end{matrix} − \frac{μM}{\sqrt{μ\overline{X}_{i}μ\overline{X}_{j}}} ∫_{D}^{∞} |φ(s)| p(s)ds\} (2.10)

provided the function Φ(λ) is non-negative at the points λ_{1}, λ_{2}, ...λ_{k−1}.

For a suitable choice of the function Φ(·) the inequality (2.10) can yield an upper bound for the difference λ_{k} − λ_{0} or for the ratio λ_{k}/λ_{0}.

3. Eigenvalues on a manifold

We apply the abstract results of the previous section to the specific situation of a Riemannian manifold M. Let us recall that, by definition, the Laplace operator associated with the Riemannian metric is represented in the local coordinates x_{1}, x_{2}, ... as follows

Δ = \frac{1}{\sqrt{g}} ∑_{i,j=1}^{dim M} \frac{∂}{∂x_{i}}\{g^{ij}\sqrt{g} \frac{∂}{∂x_{j}} \}

where g_{ij} is the contravariant metric tensor, g = det ∥g_{ij}∥, and g^{ij} = ∥g_{ij}∥^{−1}. In fact, we shall consider a slightly more general operator

L = −σ^{−1}div(σ∇)

where σ is a smooth positive function on M which looks in the coordinates as follows

L = −\frac{1}{σ\sqrt{g}} ∑_{i,j=1}^{dim M} \frac{∂}{∂x_{i}}\{g^{ij}σ\sqrt{g} \frac{∂}{∂x_{j}} \}

This operator is symmetric against the measure μ = σμ_{0} where μ_{0} = \sqrt{g}dx is the Riemannian volume so we always assume that M is equipped with the measure μ.

Our further assumptions about the manifold are completeness (so that the operator L defined initially on C_{c}^{∞}(M) has a unique self-adjoint extension which is in addition nonnegative) and finiteness of the measure μM which imply that 1 ∈ L^{2}(M, μ) and that 1 is the eigenfucntion of L to the eigenvalue 0.

Hence, the hypotheses 1^{∘}-2^{∘} of Section 1 hold. Moreover, if we put

P_{s}(λ) = cos(\sqrt{λ}s).  (3.1)

then the function family (3.1) satisfies the finite propagation speed condition 3^{∘}. We have obviously p(s) = 1.

We shall use Corollaries 2.1 and 2.2 with the properly chosen function φ(s) assuming that the subsets X, Y (or X_{0}, ...X_{k}) are given so that the distance between them is at least D > 0. The abstract inequalities (2.4) and (2.9) say that

sup_{λ∈spec_{1}} |Φ(λ)| ≥ Φ(0)\begin{matrix}√ & \overline{μXμY} \\ √ & \overline{μ\overline{X}μ\overline{Y}} \end{matrix} − \frac{μM}{\sqrt{μ\overline{X}μ\overline{Y}}} ∫_{D}^{∞} |φ(s)| p(s)ds  (3.2)

or, if we have k + 1 subsets,

sup_{λ∈spec_{k}} |Φ(λ)| ≥ inf_{i≠j} \{Φ(0)\begin{matrix}√ & \overline{μX_{i}μX_{j}} \\ √ & \overline{μ\overline{X}_{i}μ\overline{X}_{j}} \end{matrix} − \frac{μM}{\sqrt{μ\overline{X}_{i}μ\overline{X}_{j}}} ∫_{D}^{∞} |φ(s)| p(s)ds\}  (3.3)

Of course, for the latter case we have to make further assumptions about the spectrum of the operator L in the spirit of Proposition 2.2. Namely, when speaking about spec_{k}, k > 1 we shall follow the convention that the whole spectrum of L consists of discrete points λ_{0} = 0 ≤ λ_{1} ≤ λ_{2} ≤ ... ≤ λ_{k−1} with the corresponding eigenfunctions v_{0}, w_{1}, ...w_{k−1} and the rest part which lies in [λ_{k−1}, +∞). Then we denote by spec_{k} the spectrum of L in the subspace of L^{2}(M, μ) orthogonal to all w_{0}, w_{1}, ...w_{k−1}, and λ_{k} ≡ inf spec_{k}.

Of course, if the manifold M is compact then the whole spectrum is discrete, and we have infinitely many eigenvalues λ_{0} = 0 < λ_{1} ≤ λ_{2} ≤ ....

Our task will be to convert the estimates (3.2) ,(3.3) into upper bounds of the eigenvalues λ_{1}, λ_{2}, .... For any two sets X, Y ∈ M, let us introduce the notation

Q(X, Y) = \frac{(μM)^{2}}{μXμY} .  (3.4)

If X, Y do not intersect, then we have Q(x, y) ≥ 4 because μX + μY ≤ μM.

Theorem 3.1 For any pair of disjoint sets X, Y ⊂ M we have

λ_{1} < \frac{1}{D^{2}}\{1 + log Q(X, Y)\}^{2}  (3.5)

where D = dist(X, Y).

For any family of k + 1 disjoint sets X_{0}, X_{1}, ...X_{k} ⊂ M we have

λ_{k} ≤ \frac{1}{D^{2}}\{1 + sup_{i≠j} log Q(X_{i}, X_{j})\}^{2}  (3.6)

where D = inf_{i≠j} dist(X_{i}, X_{j}).

Proof of Theorem 3.1. We want the function Φ(λ) to be equal to e^{−tλ}, where t > 0 is a parameter to be optimized upon at the end of the proof. Since Φ(λ) is defined from

Φ(λ) = ∫_{0}^{∞} φ(s) cos(\sqrt{λ}s)ds

then we must take φ(s) as follows (in fact, the Fourier transform of Φ(ξ^{2}) up to constant multiples)

φ(s) = \frac{1}{\sqrt{πt}}e^{− \frac{s^{2}}{4t}}

Introducing the notations

A = \begin{matrix}√ & \overline{μXμY} \\ √ & \overline{μ\overline{X}μ\overline{Y}} \end{matrix}

and

B = \frac{μM}{\sqrt{μ\overline{X}μ\overline{Y}}}

we have by (3.2) the following inequality

e^{−λ_{1}t} ≥ A − B ∫_{D}^{∞} \frac{1}{\sqrt{πt}}e^{− \frac{s^{2}}{4t}} ds  (3.7)

We shall apply the following estimate

∫_{D}^{∞} e^{− \frac{s^{2}}{4t}} ds < \frac{2t}{D}e^{− \frac{D^{2}}{4t}}

to prove which let us set

I(D) = ∫_{D}^{∞} e^{− \frac{s^{2}}{4t}} ds

F (D) = \frac{2t}{D}e^{− \frac{D^{2}}{4t}}

and compare these functions in the following way. First of all, I(∞) = F (∞) = 0. Comparison of their derivatives shows that

F′(D) = −e^{− \frac{D^{2}}{4t}} − \frac{2t}{D^{2}} e^{− \frac{D^{2}}{4t}} < −e^{− \frac{D^{2}}{4t}} = I′(D)

whence it follows F (D) > I(D), what was to be proved.

Hence, we obtain from (3.7)

e^{−λ_{1}t} ≥ A − B\sqrt{\frac{4t}{πD^{2}}} e^{− \frac{D^{2}}{4t}} .  (3.8)

The idea of further reduction is to take t small enough so that the right hand side of (3.8) is equal to εA for some ε ∈ (0, 1) which would imply

λ_{1} ≤ \frac{1}{t} log \frac{1}{εA}.  (3.9)

Let us introduce the notation

z = \frac{D^{2}}{4t}

and rewrite (3.9) as follows

λ_{1} ≤ \frac{4}{D^{2}} z log \frac{1}{εA} ≤ \frac{4}{D^{2}} z log \frac{B}{εA} = \frac{4}{D^{2}} z log \frac{\sqrt{Q}}{ε}

where we have used B ≥ 1 and the definition (3.4) of Q = Q(X, Y) = (B/A)^{2}. On the other hand, we must have

A − B \frac{1}{\sqrt{πz}} e^{−z} = εA

or

\sqrt{z}e^{z} = \frac{B}{\sqrt{π}(1 − ε)A}  (3.10)

which defines a unique z for any ε ∈ (0, 1).

Now, we would like to find ε for which we would have in addition

z ≤ log \frac{\sqrt{Q}}{ε}  (3.11)

and, respectively,

λ_{1} ≤ \frac{4}{D^{2}}\{log \frac{\sqrt{Q}}{ε}\}^{2} .

which can be rewritten as

λ_{1} ≤ \frac{1}{D^{2}}\{log Q + 2 log \frac{1}{ε}\}^{2} .  (3.12)

Substituting (3.11) into (3.10) we obtain the inequality for ε

\sqrt{log \frac{\sqrt{Q}}{ε}} \frac{\sqrt{Q}}{ε} ≥ \frac{\sqrt{Q}}{\sqrt{π}(1 − ε)}

which is equivalent to

\sqrt{Q} ≥ ε exp \frac{1}{π}\{\frac{ε}{1 − ε}\}^{2}.  (3.13)

Since we have always Q ≥ 4 then (3.13) holds whenever its right hand side is less than 2. For example, it is true for ε = 0.65 (a slightly better value is 0.6523...) which enables us to immediately obtain (3.5) from (3.12) because 2 log \frac{1}{0.65} < 1.

The proof of (3.6) is exactly the same: take first the pair X_{i}, X_{j} which minimizes the right hand side of (3.3) , and repeat all the arguments above for this pair. Let us note that the function Φ(λ) = e^{−tλ} is positive which is essential for the proof in the case k > 1. ⊓ ⊔ Remark. Another way to resolve (3.13) is to notice that it would be implied by

\sqrt{Q} = exp \frac{1}{π}\{\frac{ε}{1 − ε}\}^{2}

whence we find ε as follows

\frac{1}{ε} = 1 + \sqrt{\frac{2}{π log Q}}.  (3.14)

Since log \frac{1}{ε} < \sqrt{\frac{2}{π log Q}} we deduce from (3.12)

λ_{1} < \frac{1}{D^{2}}\{log Q + \sqrt{\frac{8}{π log Q}}\}^{2} < \frac{1}{D^{2}}\{log Q + \frac{1.6}{\sqrt{log Q}}\}^{2}

which is better than (3.5) whenever Q > 13.

Examples.

1. Let M be a compact manifold of of non-negative Ricci curvature and let σ = 1, L = −Δ. To apply (3.5) , let us take X, Y to be two balls of radius r centered at two the most distant points of M. Since the whole manifold can be considered as a ball of the radius D = diamM then by the property of positively curved manifolds, we have

\frac{μM}{μX} ≤\{\frac{D}{r} \}^{n}

where n = dim M, and the same inequality holds for μY. Hence, (3.5) implies

λ_{1} < \frac{1}{(D − 2r)^{2}}\{1 + 2n log(D/r)\}^{2} = \frac{1}{D^{2}} \frac{1}{(1 − \frac{2}{ξ})^{2}}\{1 + 2n log ξ\}^{2}  (3.15)

where ξ = D/r. By choosing an optimal ξ ∈ (2, ∞) one can derive from (3.15)

λ_{1} < \frac{29n(n + 4)}{D^{2}}.

For comparison, let us recall the theorem of Cheng [4] which says that on a manifold in question, there holds the following sharp inequality:

λ_{1} ≤ \frac{2n(n + 4)}{D^{2}}.

2. Let M be a complete non-compact manifold with finite volume (again σ = 1 and L = −Δ), and let us denote by V (R) the volume of the exterior of the ball of radius R centered at the fixed point x_{0} ∈ M. Let X be the exterior of that ball and Y be a ball of the smaller radius R_{0} centered at the same point x_{0}. Theorem 3.1 implies that for any R > R_{0}

λ_{1} < \frac{1}{(R − R_{0})^{2}}\{1 + log \frac{(μM)^{2}}{μY} + log \frac{1}{V (R)}\}^{2} .  (3.16)

Letting R → ∞ we obtain from (3.16)

λ_{1} ≤ \underline{μ}^{2}  (3.17)

where

\underline{μ} = lim inf_{R→∞} \frac{− log V (R)}{R}.

Let us recall for comparison the theorem of Brooks [2] which says that the bottom of the essential spectrum of the Laplace operator on a complete manifold of finite volume admits the upper bound

λ_{ess} ≤ \frac{μ̄^{2}}{4}  (3.18)

where

μ̄ = lim sup_{R→∞} \frac{− log V (R)}{R}.

Virtually, (3.18) is sharper than (3.17) because λ_{1} ≤ λ_{ess} and because of the coefficient \frac{1}{4} in (3.18) . But one can easily construct examples where μ̄ = ∞ whereas \underline{μ} = 0 so the estimate (3.17) does make sense.

Comparison of (3.17) and (3.18) shows also that the upper bound (3.5) is not far from being sharp - it might be possible to improve it by a factor \frac{1}{4} but the way how the distance and the volumes are involved seems to be correct. In particular, the logarithm of the volumes enters the estimate to the correct power 2.

Let us note in this connection that it is trivial to obtain an estimate similar to (3.5) but without log . More precisely, we mean the following inequality

λ_{1} ≤ \frac{4}{D^{2}} \frac{μM}{min(μX, μY)}.  (3.19)

to prove which it suffices to construct two trial functions with disjoint supports so that the Rayleigh’s ratio for each of them is bounded by the right hand side of (3.19) . One of this functions can be taken as a standard cut-off function around X which is equal to 1 on X and vanishes off the D/2−neighbourhood of X; the second is constructed in the same way around Y.

The inequality (3.16) implies also the following upper bound for V (R)

V (R) ≤ \frac{(μM)^{2}}{μY} exp(1 − \sqrt{λ_{1}}(R − R_{0}))

which gives an exponential decay of V (R) as R → ∞ whenever λ_{1} > 0.

3. Let M be a complete manifold with finite volume, compact or non-compact, and σ = 1, L = −Δ. For any measurable set X ⊂ M, let us denote by U_{r}(X) an open rneighbourhood of X. Applying Theorem 3.1 to the sets X and Y = M \ U_{r}(X), we obtain

\overline{μ}U_{r}(X) ≥ 1 − (\overline{μ}X)^{−1} exp (1 − r\sqrt{λ_{1}(M)})  (3.20)

where \overline{μ} = (μM)^{−1}μ is the normalized measure. The inequality (3.20) reflects a “concentration phenomenon” - see [13] and [15] for details. Another inequality of this type was proved in [15] (Theorem 6.9):

\overline{μ}U_{r}(X) ≥ 1 − (1 − (\overline{μ}X)^{2}) exp (−r\sqrt{λ_{1}(M)} log (1 + \overline{μ}X)) .  (3.21)

Comparison of (3.20) and (3.21) shows that • if r\sqrt{λ_{1}(M)} < 3.11 then (3.21) is always better;

• for larger r\sqrt{λ_{1}(M)}, the inequality (3.21) is still better if \overline{μ}X is close to either 0 or 1; otherwise (3.20) provides a sharper estimate.

4. Let L be a differential operator on IR :

Lu = −σ^{−1}(σu′)′ = −u′′ − (log σ)′u′

where σ is a smooth, positive, summable function. Let us normalize it so that

∫_{−∞}^{∞} σ(x)dx = 1.

Theorem 3.1 is applicable with the measure μ = σdx. Let us take X = (x_{0}, +∞), Y = (−∞, y_{0}) where x_{0} > y_{0} are some numbers. Then D = dist(X, Y) = x_{0} − y_{0} and we have by Theorem 3.1

λ_{1} ≤ (x_{0} − y_{0})^{−2}\{1 + log \frac{1}{∫_{x_{0}}^{∞} σ(x)dx ∫_{−∞}^{y_{0}} σ(x)dx}\}^{2} .  (3.22)

In particular, if σ is the Gaussian density σ(x) = \frac{1}{\sqrt{2πα}} exp(−\frac{x^{2}}{2α}) then (3.22) yields for x_{0} = −y_{0} = 1.85\sqrt{α} (which is nearly optimal for (3.22) )

λ_{1} < \frac{5.76}{α}.

Let us recall that the exact value is λ_{1} = \frac{1}{α}.

Of course, (3.22) is not sharp numerically but, in return, it handles easily a general function σ which enters the upper bound (3.22) explicitly.

In conclusion of this section, let us observe, that Corollary 1.1 implies the following statement.

Proposition 3.1 If u, v ∈ L^{2}(M, μ) and the distance between the supports of u and v is equal to D then

|∫_{M} ve^{−tL}udμ| ≤ ∥u∥_{2}∥v∥_{2} ∫_{D}^{∞} \frac{1}{\sqrt{πt}}e^{− \frac{s^{2}}{4t}} ds.  (3.23)

Indeed, (3.23) follows directly from (1.1) if we substitute the chosen set of the functions P_{s}(λ), p(s), Φ(λ), φ(s) as above.

Let us mention also, that a similar but weaker inequality

|∫_{M} ve^{−tL}udμ| ≤ ∥u∥_{2}∥v∥_{2}e^{− \frac{D^{2}}{4t}}

was proved in [10] . See also [14] and [12] for applications.

4. Eigenvalues and the diameter of a graph

Let G be a connected finite graph on the vertex set M and the edge set E. Let us suppose that any edge ξ ∈ E is assigned a positive weight c(ξ). Then we can introduce a self-adjoint operator and a measure on the graph in the following way.

By an elementary measure μ(x) of a vertex x ∈ M we understand the sum of weights of all edges ξ coming out from x. A measure μ of any set of vertices is a sum of the elementary measures of all its vertices.

The operator L is defined as follows

Lf(x) = f(x) − ∑_{y∼x} f(y)\frac{c(\overline{xy})}{μ(x)}

where the sum is taken over all vertices y adjacent to x and \overline{xy} denotes the edge between x, y.

If all edges have the same weight then L is the combinatorial Laplace operator:

Lf(x) = f(x) − \frac{1}{d_{x}} ∑_{y∼x} f(y)

where d_{x} is the number of the edges coming out from x.

It is not difficult to see that our abstract hypotheses 1^{∘}-2^{∘} from Section 1 are fulfilled, in particular, L1 = 0.

Finally, the distance on M is defined as the combinatorial distance i.e. dist(x, y) is the smallest number of edges in a connected path of edges between the points x, y.

It is worth mentioning that the space L^{2}(M, μ) is one of finite dimension. Therefore, the operator L is bounded and can be investigated by the linear algebra methods as well. In particular, it can be represented by a finite dimensional symmetric matrix. Indeed, let us consider the operator L̂ = μ(x)^{\frac{1}{2}} Lμ(x)^{− \frac{1}{2}} in the L^{2}−space with the measure μ̂ = μ(x)^{−1}μ (i.e. μ̂ is equal to 1 on any single point set). On one hand, the spectrum of L in L^{2}(M, μ) coincides with the spectrum of L̂ in L^{2}(M, μ̂). On the other hand, since in the latter space the volume of any vertex is equal to 1 the spectrum of L̂ is nothing other than the spectrum of the matrix which represents the action of L̂ i.e.

L̂_{xy} = \{ \begin{matrix}1 & if x = y \\ −\frac{1}{\sqrt{μ(x)μ(y)}} & if x ∼ y \\ 0 & otherwise \end{matrix}

The operator L (and this matrix) has a finite spectrum 0 = λ_{0} < λ_{1} ≤ λ_{2}... ≤ λ_{N} where N + 1 is the number of vertices in M. It is not difficult to see that the whole spectrum of L lies always in [0, 2]. Moreover, we have λ_{1} ≤ 1 for any graph whose diameter is greater than 1 and λ_{N} > 1 for any graph which follows simply from the fact that the trace of L is equal to N + 1. Let us note also that λ_{N} > λ_{1} unless the graph is complete (which means that any two vertices are connected by an edge and all edges have the equal weights). More discussion on the eigenvalues λ_{i} can be found in [8] .

The main results in this Section will be stated as upper bounds of the distance between subsets of the graph involving the eigenvalues of the operator L. They will be later converted to upper bounds of the eigenvalues in the spirit of the preceding section.

For any two subsets X, Y ⊂ M, let us denote

ν(X, Y) = \begin{matrix}log & \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μX μY}} \\ log & \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}} \end{matrix} .  (4.1)

If λ_{1} = λ_{N} then the natural meaning of the right hand side of (4.1) is 0.

Theorem 4.1 We have for any disjoint subsets X, Y ⊂ M

dist(X, Y) ≤ 1 + ⌊ν(X, Y)⌋.  (4.2)

Moreover, if

ν(X, Y) ≠ 0, ν(X, Y) ≠ 1  (4.3)

then we have a slightly better inequality

dist(X, Y) ≤ ⌈ν(X, Y)⌉.  (4.4)

Remarks. The restrictions ν ≠ 0 and ν ≠ 1 are essential. The case ν = 0 takes place, for example, if Y is the complement of X. We have then dist(X, Y) = 1 and ν(X, Y) = 0 so that (4.2) is true but (4.4) is not.

To produce a counter-example for the case ν = 1, let us consider a linear graph G of 3 points \{x_{1}, x_{2}, x_{3}\} having only two edges \overline{x_{1}x_{2}} and \overline{x_{2}x_{3}} both of the weight 1. Evidently, ν(x_{1}) = 1, ν(x_{2}) = 2, ν(x_{3}) = 1. The eigenvalues of the operator L on the graph in question are equal to 0, 1, 2 with the eigenfunctions {1, 1, 1}, {1, 0, −1}, and {1, −1, 1}. Therefore, we have

\frac{λ_{N} + λ_{1}}{λ_{N} − λ_{1}} = 3.

Let X = \{x_{1}\}, Y = \{x_{3}\} then μX = μY = 1, μ\overline{X} = μ\overline{Y} = 3, and we have

\sqrt{\frac{μ\overline{X}μ\overline{Y}}{μX μY}} = 3

We see that ν(X, Y) = 1 whereas dist(X, Y) = 2. Proof of Theorem 4.1. If dist(X, Y) = 1 then there is nothing to prove. Let us assume that dist(X, Y) > 1.

We shall apply Corollary 2.1 for the proper choice of the functions and sets involved. First, we need to define the family of functions P_{s}(λ). Let us take that P_{s}(λ) is a polynomial of λ of the degree ⌊s⌋. As it follows from the definition of the operator L

suppLu ⊂ supp_{1}u

which implies that for any polynomial Q(λ) of the degree n

suppQ(L)u ⊂ supp_{n}u.

In particular,

suppP_{s}(L)u ⊂ supp_{⌊s⌋}u ⊂ supp_{s}u

so the hypothesis 3^{∘} from Section 1 holds, too.

Let us set D = dist(X, Y) and define the function φ(s) to be equal to 1 on the interval (D − 1, D) and 0 otherwise. Due to the choice of φ the integral on the right hand side of (2.4) vanishes, and we have by Corollary 2.1 the inequality

sup_{λ∈spec_{1}} |Φ(λ)| ≥ Φ(0)\sqrt{\frac{μXμY}{μ\overline{X}μ\overline{Y}}} .  (4.5)

Now, we shall specify further the polynomials P_{s}(λ). Let us take

P_{s}(λ) =\{\frac{λ_{1} + λ_{N}}{2} − λ\}^{⌊s⌋}

Therefore,

Φ(λ) = ∫_{0}^{∞} φ(s)P_{s}(λ)ds = ∫_{D−1}^{D} P_{s}(λ)ds = P_{D−1}(λ).

The inequality (4.5) yields

sup_{λ∈[λ_{1},λ_{N}]} |P_{D−1}(λ)| ≥\{\frac{λ_{1} + λ_{N}}{2} \}^{D−1} \sqrt{\frac{μXμY}{μ\overline{X}μ\overline{Y}}} .

or, since the supremum on the left hand side is equal to (\frac{λ_{N} −λ_{1}}{2} )^{D−1} we obtain

\{\frac{λ_{N} − λ_{1}}{2} \}^{D−1} ≥\{\frac{λ_{1} + λ_{N}}{2} \}^{D−1} \sqrt{\frac{μXμY}{μ\overline{X}μ\overline{Y}}}

which implies λ_{N} > λ_{1} and

D − 1 ≤ \begin{matrix}log & \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μXμY}} \\ log & \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}} \end{matrix}  (4.6)

whence (4.2) follows.

Now, let us turn to (4.4) assuming that (4.3) holds. First of all, (4.4) is sharper than (4.2) only for the integral values of ν(X, Y). Since the values 0, 1 are excluded we may suppose that ν(X, Y) ≥ 2. If, in addition, dist(X, Y) ≤ 2 then there is nothing to prove. Therefore, we may suppose also, that dist(X, Y) ≥ 3.

We want to show that, in fact, the equality in (4.6) never happens i.e.

D − 1 < \begin{matrix}log & \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μXμY}} \\ log & \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}} \end{matrix} .

which would imply (4.4) . To that end, let us return to the proof of Proposition 2.1, look into the inequality (2.3) , and realize that, in fact, under the current hypotheses we have a strong inequality there. Suppose, that we have equality in (2.3) . Let us notice that the supremum of |Φ(λ)| over spec_{1} = {λ_{1}, λ_{2}, ...λ_{N}} is equal to

\{\frac{λ_{N} − λ_{1}}{2} \}^{D−1}

and attains at exactly two points: λ = λ_{1} and λ = λ_{N}. Therefore, the equality in (2.3) may happen only if at least one of the functions u^{(1)}, v^{(1)} lies in the direct sum of the eigenspaces of λ_{1} and λ_{N}. In other words, one of those functions must be a sum of two eigenfunctions corresponding to the eigenvalues λ_{1} and λ_{N} respectively. Let it be u^{(1)}. Let us recall that u = 1_{X}, and u^{(1)} = 1_{X} − const. Hence, we must accept that there are eigenfunctions w_{1} and w_{N} of λ_{1} and λ_{N} respectively such that

w_{1} + w_{N} = 1_{X} − const.  (4.7)

If we apply the operator L to (4.7) , then we get

λ_{1}w_{1} + λ_{N}w_{N} = L1_{X}  (4.8)

The relations (4.7) , (4.8) can be solved simultaneously as a linear system which implies that w_{N} (as well as w_{1}) is a linear combination of 1_{X}, L1_{X} and 1

w_{N} = a1_{X} + bL1_{X} + c  (4.9)

with non-vanishing coefficients a, b, c.

Let y be a point in M such that dist(y, X) ≥ 3 (existence of y follows from the fact that dist(X, Y) ≥ 3.) Let us compare at this point the values of the functions w_{N} and Lw_{N} = λ_{N}w_{N}. Since the supports of 1_{X} and L1_{X} lie in the 1−neighbourhood of X, the function w_{N} must according to (4.9) be equal to the constant c at any point at the distance at least 2 from X. In particular, w_{N} ≡ c in the 1−neighbourhood of the point y which implies that Lw_{N}(y) = 0 what contradicts to the fact that Lw_{N}(y) = λ_{N}w_{N}(y) ≠ 0. ⊓ ⊔

Given subsets X, Y ⊂ M and the integer k ≥ 1, we introduce the notation

ν_{k}(X, Y) ≡ \begin{matrix}log & \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μXμY}} \\ log & \frac{λ_{N} +λ_{k}}{λ_{N} −λ_{k}} \end{matrix}

if λ_{N} > λ_{k} and ν_{k}(X, Y) = 0 otherwise.

Theorem 4.2 Let us have k + 1 disjoint subsets X_{0}, X_{1}, ...X_{k} of M and let us denote D = inf_{i≠j} dist(X_{i}, X_{j}). Then

D ≤ 1 + sup_{i≠j} ν_{k}(X_{i}, X_{j})  (4.10)

Proof. Let us consider a function family P_{s}(λ)

P_{s}(λ) =\{\frac{λ_{k} + λ_{N}}{2} − λ\}^{⌊s⌋}

and choose all other involved functions as above. Then Φ(λ) = P_{D−1}(λ) and we have obviously that Φ(λ) ≥ 0 for λ ∈ (0, λ_{k}). In particular, Φ(λ) is non-negative on {λ_{1}, λ_{2}, ...λ_{k−1}} which enables us to refer to Corollary 2.2 in order to finish the proof. ⊓ ⊔

The choice of the functions P_{s}(λ) we have used in the proof of Theorem 4.1, is not optimal. The following theorem is proved in the same way but by using the Chebychev polynomials instead in the spirit of [7] .

For any two disjoint subsets X, Y ⊂ M, let us denote

ν^{∗}(X, Y) = cosh^{−1} \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μX μY}} ; cosh^{−1} \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}}  (4.11)

and, more generally,

ν_{k}^{∗}(X, Y) ≡ cosh^{−1} \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μX μY}} ; cosh^{−1} \frac{λ_{N} +λ_{k}}{λ_{N} −λ_{k}}

for k ≥ 1. In both definitions, the right hand sides are meant to equal to 0 if λ_{N} = λ_{1} or λ_{N} = λ_{k}, respectively.

Theorem 4.3 For any two disjoint subsets X, Y ⊂ M we have

dist(X, Y) ≤ 1 + ν^{∗}(X, Y).  (4.12)

In the same way, if we are given k + 1 disjoint sets X_{0}, X_{1}, ...X_{k} ⊂ M then

inf_{i≠j} dist(X_{i}, X_{j}) ≤ 1 + sup_{i≠j} ν_{k}^{∗}(X_{i}, X_{j})

Remark. The relationship between ν(X, Y) and ν^{∗}(X, Y) is the following. They both either greater than 1, or equal to 1, or less than 1; in the first case ν^{∗}(X, Y) is less than ν(X, Y), in the second case they coincide, and in the third case ν^{∗}(X, Y) is bigger than ν(X, Y) (and the same applies for ν_{k} and ν_{k}^{∗}).

Indeed, let us put

a = cosh^{−1} \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μX μY}} b = cosh^{−1} \frac{λ_{N} + λ_{1}}{λ_{N} − λ_{1}}

then

ν^{∗} = \frac{a}{b}

while

ν = \frac{log cosh a}{log cosh b}.

Comparison of the values of ν^{∗} and ν reduces to comparison of the fractions

\frac{log cosh b}{b}, \frac{log cosh a}{a}

which follows from the fact that the function y = \frac{log cosh x}{x} is increasing for x > 0.

In particular, (4.12) implies the inequality (4.4) of Theorem 4.1 provided ν(X, Y) > 1. Indeed, if ν(X, Y) > 1 then we have from (4.12)

dist(X, Y) ≤ 1 + ν^{∗}(X, Y) < 1 + ν(X, Y)

which implies

dist(X, Y) ≤ ⌈ν(X, Y)⌉.

Proof of Theorem 4.3. Let us consider first the case of two subsets X, Y. If λ_{N} = λ_{1} then by Theorem 4.1 dist(X, Y) = 1 which implies (4.12) as well. Therefore, we can assume λ_{N} > λ_{1}.

Let us denote by T_{n}(z) the Chebychev polynomials which are defined either inductively as

T_{0}(z) = 1
T_{1}(z) = z
T_{n+1} = 2zT_{n}(z) − T_{n−1}(z), n > 1,

or, equivalently, by using the explicit formula

T_{n}(z) = \{ \begin{matrix}cosh(n cosh^{−1} z) & if |z| ≥ 1 \\ cos(n cos^{−1} z) & if |z| ≤ 1 \end{matrix} .

Let us scale the Chebychev polynomial to the interval [λ_{1}, λ_{N}] by taking

P_{s}(λ) = T_{⌊s⌋}\{\frac{λ_{N} + λ_{1} − 2λ}{λ_{N} − λ_{1}} \} .

The function φ(s) will as above be equal to 1 on (D − 1, D) and 0 otherwise, where D = dist(X, Y). Therefore, we have

Φ(λ) = P_{D−1}(λ) = T_{D−1}\{\frac{λ_{N} + λ_{1} − 2λ}{λ_{N} − λ_{1}} \} ,

and (2.4) yields

sup_{λ∈[λ_{1},λ_{N}]} |T_{D−1}\{\frac{λ_{N} + λ_{1} − 2λ}{λ_{N} − λ_{1}} \}| ≥ T_{D−1}\{\frac{λ_{N} + λ_{1}}{λ_{N} − λ_{1}} \} \sqrt{\frac{μXμY}{μ\overline{X}μ\overline{Y}}} .  (4.13)

Since

sup_{[−1,1]} |T_{n}(z)| = 1

then the left hand side of (4.13) is equal to 1, too, which implies

T_{D−1}\{\frac{λ_{N} + λ_{1}}{λ_{N} − λ_{1}} \} ≤ \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μXμY}} .

The argument of the Chebychev polynomial above is greater than 1 which enables us to solve this inequality as follows

D − 1 ≤ cosh^{−1} \sqrt{\frac{μ\overline{X}μ\overline{Y}}{μXμY}} ; cosh^{−1}\{\frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}} \}

which finishes the proof for the case k = 1.

The case k > 1 is treated in the same way by replacing everywhere λ_{1} by λ_{k} and by utilizing the fact that the Chebychev polynomials are positive on [1, +∞). ⊓ ⊔ Remark. We have not been able to slightly improve (4.12) in the same way as we have done in Theorem 4.1 by tracing back the proof of (2.3) . The point is that in contrast to the polynomial function used in the proof of Theorem 4.1, the Chebychev polynomial T_{n}(z) attains its maximum within [−1, 1] at n + 1 points which disables our previous arguments based upon the analysis of the extremal points.

Now we shall discuss some consequences of Theorems 4.1-4.3.

Corollary 4.1 If the graph is not complete then we have for any two disjoint subsets X, Y

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

where λ = λ_{1} if λ_{1} + λ_{N} ≤ 2 and λ = 1 − (λ_{N} − λ_{1})/2 otherwise.

Indeed, since μ\overline{X} < μM then we have by (4.2)

dist(X, Y) < 1 + \begin{matrix}log & \frac{μM}{\sqrt{μX μY}} \\ log & \frac{λ_{N} +λ_{1}}{λ_{N} −λ} \end{matrix}  (4.15)

or

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

Now we want to replace \frac{λ_{N} +λ_{1}}{λ_{N} −λ} by \frac{1}{1−λ} for appropriate choice of λ. We can do that whenever

\frac{λ_{N} − λ_{1}}{λ_{N} + λ} ≤ 1 − λ.  (4.17)

If λ_{N} + λ_{1} > 2 then (4.17) is true for 1 − λ = \frac{1}{2}(λ_{N} − λ_{1}). If λ_{N} + λ_{1} ≤ 2 then (4.17) is true for λ = λ_{1} because (4.17) is equivalent to

λ ≤ \frac{2λ_{1}}{λ_{N} + λ_{1}}

⊓ ⊔ Corollary 4.2 If diamG is the diameter of the graph G and m = inf_{x∈M} μ(x) then

diamG ≤ 1 + ⌊\begin{matrix}log & \{\frac{μM}{m} − 1\} \\ log & \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}} \end{matrix}⌋.  (4.18)

Indeed, let us take two the most distant points on the graph, take each of the sets X, Y to consist of one of those points, and apply Theorem 4.1. ⊓ ⊔

By using Theorem 4.3, one can replace in (4.18) the function log by the function cosh^{−1} which gives a slightly sharper estimate.

If the weights of all edges are equal to 1 (which means that the measure of any vertex is equal to the number of its neighbours) then (4.18) implies the inequality

diamG ≤ 1 + ⌊\frac{log 2 |E|}{log \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}}} ⌋  (4.19)

where |E| is the number of edges.

If the graph G is homogeneous in the sense that the measure of any vertex is the same then (4.18) implies

diamG ≤ 1 + ⌊\frac{log N}{log \frac{λ_{N} +λ_{1}}{λ_{N} −λ_{1}}} ⌋

because in that case μM/m = N + 1.

Let us introduce the k−diameter of the graph G as follows

diam_{k}G ≡ sup_{{x_{0},x_{1},...x_{k}}} inf_{i≠j} dist(x_{i}, x_{j})

where sup is spread over all subsets of M of k + 1 points. In particular, diam_{1} is the plain diameter of the graph.

Corollary 4.3 For any graph G and for any integer k ≥ 1

diam_{k}G ≤ 1 + ⌊\begin{matrix}log & \{\frac{μM}{m} − 1\} \\ log & \frac{λ_{N} +λ_{k}}{λ_{N} −λ_{k}} \end{matrix}⌋

where m = inf_{x∈M} μ(x).

In particular, if λ_{k} = λ_{N} then among any k + 1 vertices, there are two vertices which are connected by an edge.

Let us convert the inequalities of Theorems 4.1, 4.2 into upper bounds of λ_{1} and λ_{k}, respectively. For any two disjoint sets X, Y ⊂ M, let us introduce the notation

R(X, Y) = \frac{μ\overline{X}μ\overline{Y}}{μXμY}  (4.20)

For any k + 1 disjoint sets X_{0}, X_{1}, ...X_{k} ⊂ M, let us similarly define

R(X_{0}, ...X_{k}) = sup_{i≠j} \frac{μ\overline{X_{i}}μ\overline{X_{j}}}{μX_{i}μX_{j}}

Corollary 4.4 We have for any two disjoint sets X, Y ⊂ M

\frac{λ_{1}}{λ_{N}} ≤ \frac{R(X, Y)^{\frac{1}{2(D−1)}} − 1}{R(X, Y)^{\frac{1}{2(D−1)}} + 1}  (4.21)

where D = dist(X, Y) > 1. In the same way, for any k + 1 disjoint sets X_{0}, X_{1}, ...X_{k} ⊂ M

\frac{λ_{k}}{λ_{N}} ≤ \frac{R(X_{0}, ...X_{k})^{\frac{1}{2(D−1)}} − 1}{R(X_{0}, ...X_{k})^{\frac{1}{2(D−1)}} + 1}  (4.22)

where D = inf_{i≠j} dist(X_{i}, X_{j}) > 1. In particular,

\frac{λ_{1}}{λ_{N}} ≤ \frac{(μM/m)^{\frac{1}{D−1}} − 1}{(μM/m)^{\frac{1}{D−1}} + 1}  (4.23)

and

\frac{λ_{k}}{λ_{N}} ≤ \frac{(μM/m)^{\frac{1}{D_{k}−1}} − 1}{(μM/m)^{\frac{1}{D_{k}−1}} + 1}  (4.24)

where m = inf_{x∈M} μ(x), D = diamG > 1 and D_{k} = diam_{k}G > 1.

The inequalities (4.21) , (4.22) are straightforward consequences of inequalities (4.6) ,(4.10) respectively, whereas (4.23) and (4.24) follow from (4.21) and (4.22) by choosing the subsets in question to be the single vertex sets in the spirit of Corollary 4.2.

Let us note that all the inequalities (4.21) ,(4.22) ,(4.23) ,(4.24) can be considered as upper bounds for λ_{1}, λ_{k} since we always have λ_{N} ≤ 2.

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

For a subset X ⊂ M we define r−neighbourhood of X by

U_{r}(X) = {y ∈ M : dist(y, X) ≤ r}.

Theorem 4.1 implies the following result which gives a lower bound for the expansion of the neighbourhood.

Corollary 4.5 For any subset X ⊂ M and for any integer r > 1 we have

μU_{r}(X) ≥ \frac{μX}{\frac{μX}{μM} +\{1 − \frac{μX}{μM} \}\{\frac{λ_{N} −λ_{1}}{λ_{N} +λ_{1}} \}^{2(r−1)}}  (4.25)

Indeed, let us take Y = M \ U_{r}(X) so that U_{r}(X) = \overline{Y} . Then dist(X, Y) = r, and the estimate (4.25) follows from (4.6) by resolving it in μ\overline{Y} /μY. Addedremark: After this paper was written, Michel Ledoux told us (private communication) that the inequality (0.3) can be improved to

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

by using a different method. On the other hand, his method does not say anything about the higher eigenvalues.

REFERENCES

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

[2] Brooks R., On the spectrum of non-compact manifolds with finite volume, Math. Z., 187 (1984) 425-432.

[3] Cheeger J., Gromov M., Taylor M., Finite propagation speed, kernel estimates for functions of the Laplace operator, and the geometry of complete Riemannian manifolds, J. Diff. Geom., 17 (1982) 15-53.

[4] Cheng S.Y., Eigenvalue comparison theorem and its geometric application, Math. Z., 143 (1975) 289-297.

[5] Cheng S.Y., Li P., Yau S.-T., On the upper estimate of the heat kernel of a complete Riemannian manifold, Amer. J. Math., 103 (1981) no.5, 1021-1063.

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

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

[8] Chung F.R.K., “Spectral Graph Theory”, CBMS Lecture Notes, AMS publications, 1996.

[9] Chung F.R.K., Grigor’yan A., Yau S.-T., Upper bounds for eigenvalues of the discrete and continuous Laplace operators, Advances in Math., 117 165-178.

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

[11] Gaffney M. P., The harmonic operator for exterior differential forms, Proceedings of the National Academy of Sciences, USA, 37 (1951) 48-50.

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

[13] Gromov M., Milman V.D., A topological application of the isoperimetric inequality, Amer. J. Math., 105 (1983) 843-854.

[14] Li P., Yau S.-T., On the parabolic kernel of the Schrödinger operator, Acta Math., 156 (1986) no.3-4, 153-201.

[15] Milman V.D., Schechtman G., Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Math., 1200 , 1986.

[16] Sullivan D., Related aspects of positivity in Riemannian geometry, J. Diff. Geom., 25 (1987) 327-351.

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

[18] Taylor M., “Pseudodifferential operators”, Princeton Univ. Press, Princeton, 1981.

[19] Yau S.-T., Some function-theoretic properties of complete Riemannian manifolds and their applications to geometry, Indiana Math. J., 25 (1976) 659-670.