Eigenvalue inequalities for graphs and convex subgraphs

F. R. K. Chung University of Pennsylvania

Philadelphia, Pennsylvania 19104

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

Abstract

For an induced subgraph S of a graph, we show that its Neumann eigenvalue λ_{S} can be lower-bounded by using the heat kernel H_{t}(x, y) of the subgraph. Namely,

λ_{S} ≥ \frac{1}{2t} ∑_{x∈S} inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}}

where d_{x} denotes the degree of the vertex x. In particular, we derive lower bounds of eigenvalues for convex subgraphs which consist of lattice points in an d-dimensional Riemannian manifolds M with convex boundary. The techniques involve both the (discrete) heat kernels of graphs and improved estimates of the (continuous) heat kernels of Riemannian manifolds. We prove eigenvalue lower bounds for convex subgraphs of the form cϵ^{2}/(dD(M))^{2} where ϵ denotes the distance between two closest lattice points, D(M) denotes the diameter of the manifold M and c is a constant (independent of the dimension d and the number of vertices in S, but depending on the how “dense” the lattice points are). This eigenvalue bound is useful for bounding the rates of convergence for various random walk problems. Since many enumeration problems can be approximated by considering random walks in convex subgraphs of some appropriate host graph, the eigenvalue inequalities here have many applications.

1 Introduction

We consider the Laplacian and eigenvalues of graphs and induced subgraphs. Although an induced subgraph can also be viewed as a graph in its own right, it is natural to consider an induced subgraph S as having a boundary (formed by edges joining vertices in S and vertices not in S but in the “ host ” graph). The host graph then can be regarded as a special case of a subgraph with no boundary.

This paper consists of three parts. In the first part (Section 2-5), we give definitions and describe basic properties for the Laplacian of graphs. We introduce the Neumann eigenvalues for induced subgraphs and the heat kernel for graphs and induced subgraphs. Then we establish the following lower bound for the Neumann eigenvalues of induced subgraphs.

Theorem 1: For t > 0,

λ_{S} ≥ \frac{1}{2t} ∑_{x∈S} inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}}  (1)

where the detailed definitions for the eigenvalue λ_{S}, the heat kernel H_{t} and the degree d_{v} will be given later.

In the second part (Section 6-9) of the paper, we focus upon convex subgraphs. Roughly speaking, a convex subgraph has vertex set consisting of lattice points in a Riemannian manifold with a convex boundary. Our plan is to use the (continuous ) heat kernel of the convex manifold to lower-bound the (discrete) heat kernel of the induced subgraphs. To this end, we will derive an improved estimate for heat kernels of Riemannian manifold with convex boundary. Although this result is heavily motivated by the discrete problems, it is of independent interest as well. As we shall see, the discrete problems often contain additional variables, such as the number of vertices. The (continuous) heat kernel estimates in the literature usually involve constants depending (exponentially) in the dimension of the manifold. The dimension of the manifold are intimated related to the number of vertices. Consequently, such lower bounds are often too weak and too small for applications in discrete problems. In Section 9, we derive estimates with constants independent of the dimension using and strengthening a theorem of Li and Yau [9] for lower bounds of the heat kernel of a convex manifold. Under some mild conditions (e. g. the lattice points are “dense enough”), we can use the results in the continuous case to obtain eigenvalue bounds for convex subgraphs:

λ_{S} ≥ \frac{cϵ^{2}}{(d D(M))^{2}}

where ϵ denotes the distance of two closest lattice points, d is the dimension of the manifold M that S is embedded into, D(M) denotes the diameter of M and c denotes an absolute constant (see Section 9 for details). Usually, the maximum degree k of the convex subgraph is about d. The diameter D(S) of the convex subgraph S is between D(M)/ϵ and \sqrt{d}D(M)/ϵ. So, we have a lower bound for λ_{S} of the form c/(kD(S))^{2} for a general graph and of the form c/kD(S)^{2} for some graphs.

In the third part of the paper (Section 10), we discuss the relationship of Neumann eigenvalues to random walk problems. In particular, we introduce the Neumann random walk in an induced subgraph of a graph. We also generalize all the results to weighted graphs with loops. The eigenvalue lower bound then can be used to derive upper bounds for the rate of convergence for these random walks.

In the last section, we briefly discuss the applications of random walk problems to efficient approximation algorithms. In particular, we discuss the classical problems of approximating the volume of a convex body and also the problem of sampling matrices with non-negative integral entries having given row and column sums. We will use our eigenvalue inequalities to derive polynomial time upper bounds for the sampling problem which can then be used to derive efficient approximation algorithms for the enumeration problem. Since many sampling and enumeration problems often involve families of combinatorial objects which can be regarded as vertices of convex subgraphs of some appropriate host graphs, the eigenvalue bounds and the methods we describe here can be useful for many problems of this type. There are many recent developments [8, 11, 12] in approximating difficult counting problems by using the methods of random walks. The heat kernels and eigenvalue bounds in this paper offers a direct approach for bounding the eigenvalues. A number of applications in this direction will be discussed in [5].

We remark that in this pape we mainly consider Neumann eigenvalues because of the relationship with random walks. Results on Dirichlet eigenvalues will be described in a separate paper with different applications.

2 Preliminaries

We consider a graph G = (V, E) with vertex set V = V (G) and edge set E = E(G). Let d_{v} denote the degree of v. Here we assume G contains no loops or multiple edges (the generalizations to weighted graphs with loops will be discussed in Section 6). We define the matrix L with rows and columns indexed by vertices of G as follows.

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

Let T denote the diagonal matrix with the (v, v)-entry having value d_{v}. The Laplacian L of G is defined to be

L = T^{−1/2}LT^{−1/2}.

In other words, we have

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

The eigenvalues of L are denoted by 0 = λ_{0} ≤ λ_{1} ≤ ⋯ ≤ λ_{n−1}. When G is k-regular (i.e., d_{v} = k for all v), it is easy to see that

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

where A is the adjacency matrix of G.

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

\frac{⟨g, Lg⟩}{⟨g, g⟩} = \frac{⟨g, T^{−1/2}LT^{−1/2}g⟩}{⟨g, g⟩}
= \frac{⟨f, Lf⟩}{⟨T^{1/2}f, T^{1/2}f⟩}

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

where f satisfies g = T^{1/2}f and the inner product is just ⟨f_{1}, f_{2}⟩ = ∑_{x} f_{1}(x)f_{2}(x).

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

λ := λ_{1} = inf_{f⊥T 1} \frac{∑_{u∼v}(f(u) − f(v))^{2}}{∑_{v} d_{v}f(v)^{2}}  (3)

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

= inf_{g⊥T^{1/2}1} \frac{∑_{u∼v}(\frac{g(u)}{\sqrt{d}_{u}} − \frac{g(v)}{\sqrt{d}_{v}})^{2}}{∑_{v} g(v)^{2}}

Various facts about the λ_{i} can be found in [6]. In particular, an eigenfunction g having the eigenvalue λ satisfies, for all v ∈ V (G),

Lg(v) = \frac{1}{\sqrt{d_{v}}} ∑_{\begin{matrix}u \\ u∼v \end{matrix}}(\frac{g(v)}{\sqrt{d_{v}}} − \frac{g(u)}{\sqrt{d_{u}}}) = λg(v)

3 The Neumann eigenvalues of a subgraph of a graph

Let S denote a subset of the vertex set V (G) of G. The induced subgraph on S has vertex set S and edges {u, v} of E(G) with u, v ∈ S. We will often denote the induced subgraph on S also by S. There are two types of boundaries of S. The edge boundary, denoted by ∂S, consists of edges with one endpoint in S and the other endpoint not in S. The (vertex) boundary of S, denoted by δS, is defined by δS = {v ∈ V (G) : v ∉ S and {u, v} ∈ E(G) for some u ∈ V (G)}. Let S′ denote the union of edges in S and edges in ∂S. For a vertex x in δS, we let d′_{x} denote the number of neighbors of x in S. We define the Neumann eigenvalue of an induced subgraph S as follows:

λ_{S} = inf_{\begin{matrix}f \\ ∑_{x∈S} f(x)d_{x}=0 \end{matrix}} \frac{∑_{\{x,y\}∈S′}(f(x) − f(y))^{2}}{∑_{x∈S} f^{2}(x)d_{x}}  (4)

= inf_{f} sup_{c} \frac{∑_{\{x,y\}∈S′}(f(x) − f(y))^{2}}{∑_{x∈S}(f(x) − c)^{2}d_{x}}

In general, we define the i-th Neumann eigenvalue λ_{S,i} to be

λ_{S,i} = inf_{f} sup_{f′∈C_{i−1}} \frac{∑_{\{x,y\}∈S′}(f(x) − f(y))^{2}}{∑_{x∈S}(f(x) − f′(x))^{2}d_{x}}

where C_{k} is the subspace spanned by functions ϕ_{j} achieving λ_{S,j}, for 0 ≤ j ≤ k. Clearly, λ_{S,0} = 0. We use the notation that λ_{S,1} = λ_{S}.

From the discrete point of view, it is often useful to express the λ_{S,i} as eigenvalues of a matrix L_{S}. To achieve this, we first derive the following facts:

Lemma 1 Let f denote a function f : S ∪ δS → ℝ satisfying (4) with eigenvalue λ. Then f satisfies:

(a) for x ∈ S,

Lf(x) = ∑_{\begin{matrix}y \\ \{x,y\}∈S′ \end{matrix}}(f(x) − f(y)) = λf(x)d_{x},

(b) for x ∈ δS,

Lf(x) = 0

This is the so-called Neumann condition that x ∈ δS satisfies

∑_{\begin{matrix}y \\ \{x,y\}∈∂S \end{matrix}}(f(x) − f(y)) = 0

or, equivalently,

f(x) = \frac{1}{d′_{x}} ∑_{\begin{matrix}y \\ \{x,y\}∈∂S \end{matrix}} f(y)

(c) for any function h : S ∪ δS → ℝ, we have

∑_{x∈S} h(x)Lf(x) = ∑_{{x,y}∈S′}(h(x) − h(y)) · (f(x) − f(y))

We remark that the proofs of (a) and (b) follow by variational principles (cf. [6]) and (c) is a consequence of (b).

Using Lemma 1 and equation (4), we can rewrite (4) as follows by considering the operator acting on the space of functions {f : S → ℝ}, or the space of functions {f : S ∪ δS → ℝ and f satisfies the Neumann condition}.

λ_{S} = inf_{\begin{matrix}f \\ ∑ f(x)d_{x}=0 \end{matrix}} \frac{∑_{x∈S} f(x)Lf(x)}{∑_{x∈S} f^{2}(x)d_{x}}  (5)

= inf_{g⊥T^{1/2}1} \frac{∑_{x∈S} g(x)Lg(x)}{∑_{x∈S} g(x)^{2}}

= inf_{g⊥T^{1/2}1} \frac{⟨g, Lg⟩_{S}}{⟨g, g⟩_{S}}

where L is the Laplacian for the host graph G and ⟨f_{1}, f_{2}⟩_{S} = ∑_{x∈S} f_{1}(x)f_{2}(x).

For X ⊂ V, we let L_{X} denote the submatix of L restricted to columns and rows indexed by vertices in X. We define the following matrix N with rows indexed by vertices in S ∪ δS and columns indexed by vertices in S.

N(x, y) = \{ \begin{matrix}1 & if x = y, \\ 0 & if x ∈ S and x ≠ y, \\ \frac{1}{d′_{x}} & if x ∈ δS, y ∈ S and x ∼ y, \\ 0 & otherwise. \end{matrix}

Further, we define an |S| × |S| matrix

L_{S} = T^{−1/2}N^{∗}L_{S∪δS}NT^{−1/2}

where N^{∗} denotes the transpose of N.

It is easy to see from equation (5) that the λ_{S,i} are exactly the eigenvalues of L_{S}.

4 The heat kernel of a subgraph

Suppose for a graph G and an induced subgraph S of n vertices of G, we write the Laplacian of S in the form:

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

where P_{i} is the projection of L to the i-th Neumann eigenfunction φ_{i} of the induced subgraph S. The heat kernel H_{t} of S , for t ≥ 0, is defined to be the following n × n matrix:

H_{t} = ∑_{i} e^{−λ_{i}t}P_{i}
= e^{−tL}
= I − tL + \frac{t^{2}}{2} L^{2} − …

In particular, H_{0} = I. In the special case that S is taken to be the vertex set of G, H_{t} is the heat kernel of the host graph G.

For a function f : S ∪ δS → ℝ, we consider

F (t, x) = ∑_{y∈S∪δS} H_{t}(x, y)f(y)  (6)
= (H_{t}f)(x).  (7)

Here are some useful facts about F and H_{t}.

Lemma 2

(i) F (0, x) = f(x)

(ii) For x ∈ S ∪ δS,

∑_{y∈S∪δS} H_{t}(x, y)\sqrt{d_{y}} = \sqrt{d_{x}}

(iii) F satisfies the heat equation

\frac{∂F}{∂t} = −LF

.

(iv) For any vertex x in δS,

LF (t, x) = ∑_{\begin{matrix}y \\ \{x,y\} \end{matrix}}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}}) = 0

(v) For any function G : ℝ × V → ℝ, we have

∑_{\{x,y\}∈S′}(\frac{G(t, x)}{\sqrt{d_{x}}} − \frac{G(t, y)}{\sqrt{d_{y}}})(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}}) = ∑_{x∈S} G(t, x)LF (t, x)

Proof: (i) is obvious and (ii) follows by considering the function T^{1/2}1 as the function f in (6):

∑_{y} H_{t}(x, y)\sqrt{d_{y}} = (H_{t}T^{1/2}1)(x)
= T^{1/2}1(x)
= \sqrt{d_{x}}

To see (iii) we have

\frac{∂F}{∂t} = \frac{∂}{∂t}H_{t}f
= \frac{∂}{∂t}e^{−tL}f
= −LF

The proof of (iv) follows from the fact that all eigenfunctions ϕ_{i} with corresponding F_{i} in (6) satisfy (iv).

To prove (v), we have

∑_{x∈S} G(t, x)LF (t, x) = ∑_{x∈S} F (t, x)T^{−1/2}LT^{−1/2}F (t, x)

= ∑_{x∈S} \frac{G(t, x)}{\sqrt{d_{x}}} ( ∑_{\begin{matrix}y \\ \{x,y\}∈S′ \end{matrix}}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}}))

= ∑_{x∈S∪δS} \frac{G(t, x)}{\sqrt{d_{x}}} ( ∑_{\begin{matrix}y \\ \{x,y\}∈S′ \end{matrix}}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}}))

= ∑_{\begin{matrix}y \\ \{x,y\}∈S′ \end{matrix}}(\frac{G(t, x)}{\sqrt{d_{x}}} − \frac{G(y, t)}{\sqrt{d_{y}}})(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (y, t)}{\sqrt{d_{y}}})

by using (iv).

Lemma 3 For all x, y ∈ S ∪ δS, we have H_{t}(x, y) ≥ 0. Proof: For a fixed y, we define H(t, x) = H_{t}(x, y). Let χ denote the characteristic function

χ(H(t, x)) = \{ \begin{matrix}1 & if H(t, x) < 0, \\ 0 & otherwise. \end{matrix}

We consider

\frac{d}{dt} ∑_{x∈S∪δS} H^{2}(t, x)χ(H(t, x))

= 2 ∑_{x∈S∪δS} H(t, x)\frac{d}{dt}H(t, x) + ∑_{x∈S∪δS} H^{2}(t, x)\frac{d}{dt}χ(H(t, x))
= I + II.

We deal with I and II separately.

I = ∑_{x∈S∪δS} H(t, x)\frac{d}{dt}H(t, x)
= − ∑_{x∈S∪δS} H(t, x)LH(t, x)
= − ∑_{\{x,y\}∈S′}(\frac{H(t, x)}{\sqrt{d_{x}}} − \frac{H(t, y)}{\sqrt{d_{y}}})^{2}
≤ 0

since LH(t, x) = 0 for x ∈ δS. Also, we have

II = ∑_{x∈S∪δS} H^{2}(t, x)\frac{d}{dt}χ(H(t, x))
= 0

since \frac{d}{dt}χ(H(t, x)) = 0 if H(t, x) ≠ 0.

Therefore we have

∑_{x∈S∪δS} H^{2}(t, x)χ(H(t, x)) ≤ ∑_{x∈S∪δ(S)} H^{2}(0, x)χ(H(0, x)) = 0

This implies χ(H_{t}(x, y)) = 0 and Lemma 3 is proved.

5 An eigenvalue inequality

In this section, we will prove the following inequality involving the eigenvalue λ_{S} of an induced subgraph S with a heat kernel H_{t}(x, y).

λ_{S} ≥ \frac{1}{2t} ∑_{x∈S} inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}}

To do so, we consider a given function f : S ∪ δS → ℝ, and we define

g(x, t) = ∑_{y∈S} H_{t}(x, y)\sqrt{d_{x}d_{y}}(\frac{f(y)}{\sqrt{d_{y}}} − \frac{F (t, x)}{\sqrt{d_{x}}})^{2}.  (8)

where F (t, x) = H_{t} f(x). By using Lemma 2 (ii), we have

g(x, t) = ∑_{y∈S} H_{t}(x, y)\sqrt{d_{x}/d_{y}}f^{2}(y) − F^{2}(t, x)  (9)

By summing over x in S, we obtain

∑_{x∈S} g(x, t) = ∑_{x∈S} ∑_{y∈S} H_{t}(x, y)\sqrt{d_{x}/d_{y}}f^{2}(y) − ∑_{x∈S} F^{2}(t, x)

Using Lemma 2 (i),(ii), (iv) and (v), we get

∑_{x∈S} g(t, x) = ∑_{y∈S} f^{2}(y) − ∑_{x∈S} F^{2}(t, x)
= − ∫_{0}^{t} \frac{d}{ds} · ∑_{x∈S} F^{2}(s, x) ds
= −2 ∫_{0}^{t} ∑_{x∈S} F (s, x)\frac{d}{ds}F (s, x) ds
= 2 ∫_{0}^{t} ∑_{x∈S} F (s, x)LF (s, x) ds
= 2 ∫_{0}^{t} ∑_{\{x,y\}∈S′}(\frac{F (s, x)}{\sqrt{d_{x}}} − \frac{F (s, y)}{\sqrt{d_{y}}})^{2} ds  (10)

We claim that for any t ≥ 0, we have

Fact 1: ∑_{\{x,y\}∈S′}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}})^{2} ≤ ∑_{\{x,y\}∈S′}(\frac{f(x)}{\sqrt{d_{x}}} − \frac{f(y)}{\sqrt{d_{y}}})^{2}

To see this, we consider

\frac{d}{dt} ∑_{\{x,y\}∈S′}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}})^{2}

= 2 ∑_{\{x,y\}∈S′}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}})(\frac{d}{dt} \frac{F (t, x)}{\sqrt{d_{x}}} − \frac{d}{dt} \frac{F (t, y)}{\sqrt{d_{y}}})
= 2 ∑_{x∈S∪δS} \frac{d}{dt} \frac{F (t, x)}{\sqrt{d_{x}}} ∑_{\begin{matrix}y \\ \{x,y\}∈S′ \end{matrix}}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}})
= 2 ∑_{x∈S∪δS} \frac{d}{dt}F (t, x)LF (t, x)
= −2 ∑_{x∈S} \frac{d}{dt}F (t, x) · \frac{d}{dt}F (t, x)
= −2 ∑_{x∈S}(\frac{d}{dt}F (t, x))^{2}
≤ 0

Therefore

∑_{\{x,y\}∈S′}(\frac{F (t, x)}{\sqrt{d_{x}}} − \frac{F (t, y)}{\sqrt{d_{y}}})^{2} ≤ ∑_{\{x,y\}∈S′}(\frac{F (0, x)}{\sqrt{d_{x}}} − \frac{F (0, y)}{\sqrt{d_{y}}})^{2}
= ∑_{\{x,y\}∈S′}(\frac{f(x)}{\sqrt{d_{x}}} − \frac{f(y)}{\sqrt{d_{y}}})^{2}

Thus, Fact 1 is proved.

Substituting the inequality of Fact 1 into (10), we obtain

∑_{x∈S} g(t, x) = 2 ∫_{0}^{t} ∑_{\{x,y\}∈S′}(\frac{F (s, x)}{\sqrt{d_{x}}} − \frac{F (s, y)}{\sqrt{d_{y}}})^{2}ds
≤ 2t ∑_{\{x,y\}∈S′}(\frac{f(x)}{\sqrt{d_{x}}} − \frac{f(y)}{\sqrt{d_{y}}})^{2}  (11)

In the other direction, we consider the lower bound:

∑_{x∈S} g(t, x) = ∑_{x∈S} ∑_{y∈S} H_{t}(x, y)\sqrt{d_{x}d_{y}}(\frac{f(y)}{\sqrt{d_{y}}} − \frac{F (t, x)}{\sqrt{d_{x}}})^{2}
≥ ∑_{x∈S} (inf_{y∈S} H_{t}(x, y)\sqrt{\frac{d_{x}}{d_{y}}} ) ∑_{y∈S}(\frac{f(y)}{\sqrt{d_{y}}} − \frac{F (t, x)}{\sqrt{d_{x}}})^{2}d_{y}
≥ ∑_{x∈S} (inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}} ) (inf_{c∈ℝ} ∑_{y}(\frac{f(y)}{d_{y}} − c)^{2}d_{y})  (12)

Combining (11) and (12), we have

sup_{c} \frac{∑_{\{x,y\}∈S′}(\frac{f(x)}{\sqrt{d_{x}}} − \frac{f(y)}{\sqrt{d_{y}}})^{2}}{∑_{y∈S}(\frac{f(y)}{\sqrt{d_{y}}} − c)^{2}d_{y}} ≥ \frac{∑_{x∈S} inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}}}{2t}

For the definition in (3), the left-hand side of the above inequality is exactly λ_{S}. Therefore we have proved the following:

Theorem 1 The Neumann eigenvalue λ_{S} for an induced subgraph S satisfies

λ_{S} ≥ \frac{1}{2t} ∑_{x∈S} inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}}

6 Bounding eigeinvalues using the heat kernels

In this section, we will discuss various techniques of using the eigenvalue inequality in Theorem 1. To lower bound λ_{S}, one approach is to find some other function to serve as a lower bound for H_{t}. We will describe several sufficient conditions for establishing lower bounds for H_{t}.

Let k denote a function

k : R × V × V → ℝ

For convenience, we will sometimes suppress the variable y and write

k(t, x) = k(t, x, y)

for a fixed y. Suppose k satisfies the following three conditions (A), (B) and (C), for a fixed ϵ > 0 and t ≥ 0.

(A) \frac{∂}{∂t}k(t, x) ≤ −Lk(t, x) + ϵk(t, x)

(B) k(ϵ′, x, x) = 1 and k(ϵ′, x, y) = 0 for x, y ∈ S and x ≠ y.

(C) For all x ∈ δS,

∑_{\begin{matrix}x′∈S \\ \{x,x′\}∈S′ \end{matrix}}(\frac{k(t, x)}{\sqrt{d_{x}}} − \frac{k(t, x′)}{\sqrt{d_{x′}}}) ≤ 0

Theorem 2 Suppose S is an induced subgraph with the heat kernel H_{t}. If k satisfies (A),(B) and (C) for fixed ϵ and for all t ≥ 0, then for x, y ∈ S, we have

H_{t}(x, y) ≥ k(t, x, y) e^{−ϵt}

Proof: Suppose we define

ĥ(t, x, y) = e^{ϵt}H_{t}(x, y)

Then we have

\frac{∂}{∂t}ĥ = ϵĥ − Lĥ  (13)

Using (B), we find:

∫_{0}^{t} \frac{∂}{∂s} ∑_{z∈S} ĥ(t − s, x, z)k(s, z, y)ds

= ∑_{z∈S}[ĥ(0, x, z) · k(t, z, y) − ĥ(t, x, z) · k(0, z, y)]
= k(t, x, y) − ĥ(t, x, y)

Therefore, for fixed x and y in S, we have

−ĥ(t, x, y) + k(t, x, y)

= ∫_{0}^{t} \frac{∂}{∂s} ∑_{z∈S} ĥ(t − s, x, z)k(s, z, y)ds

≤ ∫_{0}^{t} ∑_{z∈S}(\frac{∂}{∂s}ĥ(t − s, x, z) · k(s, z, y) + ĥ(t − s, x, z) · \frac{∂}{∂s}k(s, z, y)]ds

≤ ∫_{0}^{t} ∑_{z∈S}[L_{z}ĥ(t − s, x, z) · k(s, z, y) − ϵĥ(t − s, x, z)k(s, z, y)

+ĥ(t − s, x, z)\frac{∂}{∂s}k(s, z, y)]ds [by (13)]

≤ ∫_{0}^{t} [∑_{z∈S} L_{z}ĥ(t − s, x, z) · k(s, z, y) − ∑_{z∈S} ĥ(t − s, x, z) · L_{z}k(s, z, y)] ds

[by (A)]

Since the Neumann condition implies

L_{z}(t − s, x, z) = 0

for z ∈ δS, the above sum is equal to

∫_{0}^{t} [ ∑_{z∈S∪δS} L_{z}ĥ(t − s, x, z) · k(s, z, y) − ∑_{z∈S} ĥ(t − s, x, z) · L_{z}k(s, z, y)] ds

= ∫_{0}^{t}[ ∑_{\{z,z′\}∈S′}(\frac{ĥ(t − s, x, z)}{\sqrt{d_{z}}} − \frac{ĥ(t − s, x, z′)}{\sqrt{d_{z′}}}) · (\frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}})

− ∑_{z∈S} ĥ(t − s, x, z) · L_{z}k(s, z, y)]ds

= ∫_{0}^{t} ∑_{z∈δS} \frac{ĥ(t − s, x, z)}{\sqrt{d_{z}}}( ∑_{\begin{matrix}z′∈S \\ \{z,z′\}∈S′ \end{matrix}} \frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}})ds

≤ 0 where the last inequality follows from the fact that ĥ ≥ 0 and the last term

∑_{\begin{matrix}z′∈S \\ \{z,z′\}∈S′ \end{matrix}} \frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}} is ≤ 0 by using condition (C). Therefore we have

ĥ(t, x, y) ≥ k(t, x, y)

as desired. The proof of Theorem 2 is complete.

We now consider a modified version of (B). For some ϵ′ > 0, (B’) k(ϵ′, x, x) = 1 and k(ϵ′, x, y) < ϵ′′\sqrt{d_{x}d_{y}} for x, y ∈ S and x ≠ y. Theorem 3 Suppose S is an induced subgraph with the heat kernel H_{t}. If k satisfies (A),(B’) and (C) for fixed ϵ, ϵ′, ϵ′′ and for all t ≥ ϵ′, then for x, y ∈ S, we have

H_{t−ϵ′}(x, y) + ϵ′′\sqrt{d_{x}d_{y}} ≥ k(t, x, y) e^{−ϵt}

Proof: We follow the proof of Theorem 2. By (B’), we have:

∫_{ϵ′}^{t} \frac{∂}{∂s} ∑_{z∈S} ĥ(t − s, x, z)k(s, z, y)ds

= ∑_{z∈S}[ĥ(0, x, z) · k(t, z, y) − ĥ(t − ϵ′, x, z) · k(ϵ′, z, y)]
≥ k(t, x, y) − ĥ(t − ϵ′, x, y) − ϵ′′ ∑_{z} ĥ(t − ϵ′, x, z)\sqrt{d_{y}d_{z}}
≥ k(t, x, y) − ĥ(t − ϵ′, x, y) − ϵ′′\sqrt{d_{x}d_{y}}e^{ϵ(t−ϵ′)}

by using the fact that ∑_{y} H_{t}(x, y)\sqrt{d_{y}} = \sqrt{d_{x}}. Therefore, for fixed x and y in S, we have −ĥ(t − ϵ′, x, y) + k(t, x, y) − ϵ′′\sqrt{d_{x}d_{y}}e^{ϵ(t−ϵ′)}

≤ ∫_{ϵ′}^{t} \frac{∂}{∂s} ∑_{z∈S} ĥ(t − s, x, z)k(s, z, y)ds

≤ ∫_{ϵ′}^{t} ∑_{z∈S}(\frac{∂}{∂s}ĥ(t − s, x, z) · k(s, z, y) + ĥ(t − s, x, z) · \frac{∂}{∂s}k(s, z, y)]ds

≤ ∫_{ϵ′}^{t} ∑_{z∈S}[L_{z}ĥ(t − s, x, z) · k(s, z, y) − ϵĥ(t − s, x, z)k(s, z, y)

+ĥ(t − s, x, z)\frac{∂}{∂s}k(s, z, y)]ds [by (13)]

≤ ∫_{ϵ′}^{t} [ ∑_{z∈S∪δS} L_{z}ĥ(t − s, x, z) · k(s, z, y) − ∑_{z∈S} ĥ(t − s, x, z) · L_{z}k(s, z, y)] ds

[by (A)]

= ∫_{ϵ′}^{t}[ ∑_{\{z,z′\}∈S′}(\frac{ĥ(t − s, x, z)}{\sqrt{d_{z}}} − \frac{ĥ(t − s, x, z′)}{\sqrt{d_{z′}}}) · (\frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}})

− ∑_{z∈S} ĥ(t − s, x, z) · L_{z}k(s, z, y)]ds

= ∫_{ϵ′}^{t} ∑_{z∈δS} \frac{ĥ(t − s, x, z)}{\sqrt{d_{z}}}( ∑_{\begin{matrix}z′∈S \\ \{z,z′\}∈S′ \end{matrix}} \frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}})ds

≤ 0 Therefore we have

H_{t−ϵ′}(x, y) + ϵ′′\sqrt{d_{x}d_{y}} ≥ k(t, x, y)e^{−ϵt}

Next, we consider the following variation of condition (A):

(A’) \frac{∂}{∂t}k(t, x) ≤ −Lk(t, x) + \frac{ϵ_{0}}{t^{2}} k(t, x) for t satisfying t_{0} ≥ t ≥ ϵ′.

Theorem 4 Suppose S is an induced subgraph with the heat kernel H_{t}. If k satisfies (A’),(B’) and (C) for fixed t_{0}, ϵ_{0}, ϵ′, ϵ′′ and for all t_{0} ≥ t ≥ ϵ′. Then for x, y ∈ S, we have

H_{t_{0}−ϵ′}(x, y) + ϵ′′\sqrt{d_{x}d_{y}} ≥ (1 − ϵ′′)k(t_{0}, x, y) e^{−3ϵ_{0}/ϵ′}

Proof: We consider the following function

h̄(t, x, y) = e^{3ϵ_{0}/(t_{0}+2ϵ′−t)}H_{t}(x, y)

Then we have

\frac{∂}{∂t}h̄ = \frac{3ϵ_{0}}{(t_{0} + 2ϵ′ − t)^{2}} h̄ − Lh̄  (14)

The following calculation is similar but slightly different to that in the proof of Theorem 3. For t satisfying t_{0} ≥ t ≥ ϵ′, we have

−h̄(t_{0} − ϵ′, x, y) + k(t_{0}, x, y) − ϵ′′\sqrt{d_{x}d_{y}}d^{2ϵ_{0}/ϵ′}

≤ ∫_{ϵ′}^{t_{0}} \frac{∂}{∂s} ∑_{z∈S} h̄(t − s, x, z)k(s, z, y)ds

≤ ∫_{ϵ′}^{t_{0}} ∑_{z∈S}(\frac{∂}{∂s}h̄(t_{0} − s, x, z) · k(s, z, y) + h̄(t_{0} − s, x, z) · \frac{∂}{∂s}k(s, z, y)]ds

≤ ∫_{ϵ′}^{t_{0}} ∑_{z∈S}[L_{z}h̄(t_{0} − s, x, z) · k(s, z, y) − \frac{3ϵ_{0}}{(2ϵ′ + s)^{2}} h̄(t_{0} − s, x, z)k(s, z, y)

+h̄(t_{0} − s, x, z)\frac{∂}{∂s}k(s, z, y)]ds

≤ ∫_{ϵ′}^{t_{0}} ∑_{z∈S}[L_{z}h̄(t_{0} − s, x, z) · k(s, z, y) − \frac{ϵ_{0}}{s^{2}} h̄(t_{0} − s, x, z)k(s, z, y)

+h̄(t_{0} − s, x, z)\frac{∂}{∂s}k(s, z, y)]ds

≤ ∫_{ϵ′}^{t_{0}} [ ∑_{z∈S∪δS} L_{z}h̄(t_{0} − s, x, z) · k(s, z, y) − ∑_{z∈S} h̄(t_{0} − s, x, z) · L_{z}k(s, z, y)] ds

= ∫_{ϵ′}^{t_{0}}[ ∑_{\{z,z′\}∈S′}(\frac{h̄(t_{0} − s, x, z)}{\sqrt{d_{z}}} − \frac{h̄(t_{0} − s, x, z′)}{\sqrt{d_{z′}}}) · (\frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}})

− ∑_{z∈S} h̄(t_{0} − s, x, z) · L_{z}k(s, z, y)]ds

\begin{matrix}= ∫_{ϵ′}^{t_{0}} ∑_{z∈δS} \frac{h̄(t_{0} − s, x, z)}{\sqrt{d_{z}}}( ∑_{\begin{matrix}z′∈S \\ \{z,z′\}∈S′ \end{matrix}} \frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}})ds \\ ≤ 0 \end{matrix}

Therefore we have

H_{t_{0}−ϵ′}(x, y) + ϵ′′\sqrt{d_{x}d_{y}} ≥ k(t, x, y)e^{−3ϵ_{0}/ϵ′}

and Theorem 4 is proved.

We consider another variation of condition (C):

(C’) | ∑_{\begin{matrix}x′ \\ \{x,x′\}∈S′ \end{matrix}} \frac{k(t, x)}{\sqrt{d_{x}}} − \frac{k(t, x′)}{\sqrt{d_{x′}}} | ≤ \frac{ϵ_{1}k(t, x)\sqrt{d_{x}}}{\sqrt{t}} for x ∈ S.

Theorem 5 Suppose k satisfies (A’), (B’) and (C’) for fixed t_{0}, ϵ_{0}, ϵ′, ϵ′′ and all t satisfying t_{0} ≥ t ≥ ϵ′. Then, we have

H_{t_{0}−ϵ′}(x, y) + ϵ′′\sqrt{d_{x}d_{y}} ≥ (1 − \frac{2c′ϵ_{1}}{\sqrt{t_{0}}} ) min_{|t_{0}−s|≤ϵ′} k(s, x, y)e^{−3ϵ_{0}/ϵ′}

provided for some c′ ≥ 1, c′ϵ_{1}/\sqrt{t}_{0} ≤ 1/4 and for t_{0} ≥ t ≥ ϵ′,

∑_{z∈∂S} k(t − s, x, z)k(s, z, y) ≤ \frac{c′}{t} k(t, x, y)  (15)

for x, y ∈ S. Proof: Suppose the contrary. Following the proof of Theorem 4, we have

|h̄(t_{0} − ϵ′, x, y) − k(t, x, y) + ϵ′′\sqrt{d_{x}d_{y}}e^{3ϵ_{0}/ϵ′}|

≤ ∫_{ϵ′}^{t_{0}} ∑_{z∈δS} \frac{h̄(t_{0} − s, x, z)}{\sqrt{d_{z}}}( ∑_{\begin{matrix}z′∈S \\ \{z,z′\}∈S′ \end{matrix}} |\frac{k(s, z, y)}{\sqrt{d_{z}}} − \frac{k(s, z′, y)}{\sqrt{d_{z′}}}|)ds
≤ ϵ_{1} ∫_{ϵ′}^{t_{0}} \frac{1}{\sqrt{s}} ∑_{z∈δS} h̄(t_{0} − s, x, z)k(s, z, y)ds

We consider

X = sup_{x,y,t_{0}≥t≥ϵ′} \frac{|h̄(t, x, y) − k(t, x, y)|}{k(t, x, y)}

We have, by using (15)

|h̄(t − ϵ′, x, y) − k(t, x, y) + ϵ′′\sqrt{d_{x}d_{y}}e^{3ϵ_{0}/ϵ′}|
≤ ϵ_{1} ∫_{ϵ′}^{t_{0}} \frac{1}{\sqrt{s}} ∑_{z∈δS}[|h̄(t_{0} − s, x, z) − k(t_{0} − s, x, z)| + k(t_{0} − s, x, z)]k(s, z, y)ds

≤ ϵ_{1} ∫_{ϵ′}^{t_{0}} \frac{1}{\sqrt{s}} ∑_{z∈δS} \frac{ϵ_{1}c′}{\sqrt{s}} (X + 1)k(t_{0}, x, y)ds

≤ \frac{ϵ_{1}c′}{\sqrt{t_{0}}} (X + 1)k(t_{0}, x, y)

Therefore we have

H_{t_{0}−ϵ′}(x, y) + ϵ′′\sqrt{d_{x}d_{y}} ≥ (1 − \frac{2c′ϵ_{1}}{\sqrt{t_{0}}} ) min_{|t_{0}−s|≤ϵ′} k(s, x, y)e^{−3ϵ_{0}/ϵ′}

and Theorem 5 is proved.

7 Convex subgraphs embedded in a manifold

In previous sections, we considered general graphs. In the remainder of this paper, we will restrict ourselves to special subgraphs of homogeneous graphs that are embedded in Riemannian manifolds. Such a restriction will allow us to derive eigenvalue bounds for graphs using known results for eigenvalues of Riemannian manifolds. The restricted classes of graphs still include many families of graphs which arise in various applications in enumeration and sampling. Roughly speaking, our plan here is to modify the heat kernels of the Riemannian manifolds with convex boundary which can then serve as lower-bound functions of k(t, x, y) in Section 3.

We start with some definitions. Let Γ = (V, E) denote a graph with vertex set V = V (Γ) and edge set E = E(Γ). We say that Γ is a homogeneous graph with an associated group H acting on V if the following two conditions are satisfied:

(i) for any g ∈ H, {gu, gv} ∈ E if and only if {u, v} ∈ E,

(ii) for any two vertices u and v, there is a g ∈ H such that gu = v.

Thus Γ is vertex-transitive under the action of H and the vertex set V can be identified with the coset space H/I where I = {g ∈ H : gv = v} , for a fixed vertex v, is the isotropy group. We note that a Cayley graph is the special case of a homogeneous graph with I trivial. The edge set of a homogeneous graph Γ can be described by an edge generating set K ⊂ H such that each edge of Γ is of the form {v, gv} for some v ∈ V, and g ∈ K. We also require the generating set K to be symmetric, i.e., g ∈ K if and only if g^{−1} ∈ K.

We will first defined a simple version of a lattice graph. Suppose the vertices of Γ can be embedded into a Riemannian manifold M with a distance function μ such that

μ(x, gx) = μ(y, g′y) ≤ μ(x, y)  (16)

for any g, g′ ∈ K and x, y ∈ V (Γ). Then Γ is called a simple lattice graph. We say that Γ is a lattice graph if for a vertex x, every lattice point in the convex hull formed by gx, g ∈ K is adjacent to x.

An induced subgraph on a subset S of a lattice graph Γ is said to be convex if there is a submanifold M ⊂ M with a convex boundary ∂M ≠ ϕ such that S consists of all vertices of Γ in the interior of M. Furthermore, suppose that M is d-dimensional and we require that all d-dimensional balls centered at a vertex x of S of radius ϵ/2 are contained in M.

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

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

It is easy to see that Γ is a homogeneous graph with the edge generating set consisting of

all 2 × 2 submatrices ( \begin{matrix}1 & −1 \\ −1 & 1 \end{matrix} ). Obviously, Γ can be viewed as being embedded in the

mn-dimensional Euclidean space M = ℝ^{mn}. In fact, Γ is embedded in the submanifold M of the (mn−m−n+1)-dimensional subspace containing the vertices of Γ. M is determined by

∑_{j} x_{ij} = r_{i}

∑_{i} x_{ij} = c_{i}

x_{ij} ≥ −\frac{1}{2}

It is easy to verify that S is a convex subgraph of the lattice graph Γ.

Remark 1: In [3], the authors consider a “strongly” convex subgraph S of a homogeneous graph. An eigenvalue bound was derived by using an entirely different approach. Namely, the following Harnack inequality was established for an eigenfunction f of S and for any vertex x,

∑_{y∼x}(f(x) − f(y))^{2} ≤ 8λ max_{y∈S} f^{2}(y)

This can be used to show

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

where k is the maximum degree of T and D denotes the diameter of T. The differences between the two definitions of convexity can be described as follows: In [3], a strongly convex subgraph T requires that for any two vertices u and v in T, all shortest paths joining u and v in the homogeneous graph must be contained in T. Here, the convexity condition requires the embedding of the subgraph into a Riemannian manifold with a convex boundary. We remark that various applications involving random walks on graphs which can often be interpreted as occurring in convex subgraphs (but not strongly convex subgraphs) of some appropriate homogeneous graph. For example, the convex subgraphs mentioned in Example 1 are not strongly convex.

8 Bounding the discrete heat kernel by the continuous heat kernel

Let S denote a convex subgraph of a lattice graph Γ with edge-generating set K. Let M denote the associated d-dimensional manifold M with a convex boundary and let μ denote the distance function on M. In this section, we restrict ourselves to the case of convex subgraphs of simple lattice graphs so that the discussions are simpler but contain the essence of the general case.

Let h(t, x, y) denote the heat kernel of M and suppose u(t, x) = h(t, x, y) satisfies the heat equation

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

with the Neumann boundary condition

\frac{∂}{∂ν} u(t, x) = 0  (17)

where Δ denotes the Laplace operator of the form

Δ = ∑_{i,j} a_{i,j} \frac{∂^{2}}{∂x_{i} ∂x_{j}}

and a_{i,j} depends on the edge generating set K as described later in (19). We remark that the convexity condition (17) is later on used to give heat kernel estimates. Our results can be applied to subgraphs corresponding to manifolds with weaker convexity conditions as long as the heat kernel estimates for manifolds can still be derived.

We assume that μ(x, gx) = ϵ for all x ∈ V (Γ) and g ∈ K. To proceed, we define the function k(t, x, y) which will be used later with Theorem 2.

k(t, x, y) = c_{1} ∫_{M} h(c_{2} t, x − z, y)φ(z)dz

where φ is a bell-shaped function (such as a modified Gaussian function exp(−c′|z/ϵ|^{2}) ) with compact support, say, {|z| < ϵ/4}, and which satisfies

c_{1} ∫ φ(z)dz = c_{3} (c_{4}ϵ)^{d}

where c_{3} and c_{4} are chosen so that the above quantity is within a constant factor of the volume of the Voronoi region R_{x} = {y : μ(y, x) ≤ μ(y, z) for all z ∈ Γ ∩ M}, for a vertex x. So, k(t, x, y) can be approximated by h(c_{2}t, x, y)U or

∫_{R_{x}} h(c_{2}t, z, y)dz  (18)

when t is not too small. by using the gradient estimates of h in the next section. Here U denotes the maximum over x of the volume of R_{x}.

In order to use Theorem 2, we need to verify conditions (A’), (B’) and (C’). First we want to show:

\frac{∂}{∂t}k(t, x) ≤ −Lk(t, x) + \frac{ϵ_{0}}{t^{2}} k(t, x)

for t_{0} ≥ t ≥ ϵ′ = d/log volS. where ϵ_{0} = \frac{c_{5}ϵ^{4}d}{c_{2}}. Here we suppress y and write k(t, x, y) = k(t, x). Note that we have

\frac{∂}{∂t}k(t, x) = c_{1} ∫_{M} \frac{∂}{∂t}h(c_{2} t, x − z)φ(z)dz
= c_{1} ∫_{M} c_{2} Δh(c_{2} t, x − z)φ(z)dz

Also,

Lk(t, x) = k(t, x) − \frac{1}{d_{x}} ∑_{y∼x} k(t, y)
= c_{1} ∫_{M} Lh(c_{2}t, x − z)φ(z)dz

Here we use the convention of identifying a vertex with the associated point in the ddimensional manifold M. For simplicity, we write gx = g + x. (Formally we should use an appropriate mapping σ from V to M so that σ(gx) = σ(g) + σ(x). For a fixed g ∈ K, we consider the two terms in the sum involving g and g^{−1}:

[φ(y) − φ(y + g)] + [φ(y) − φ(y − g)] = −[φ(y + g) − φ(y)] + [φ(y) − φ(y − g)]

which can be approximated by the second partial derivative in the direction of g scaled by a factor of ϵ^{2}. Therefore the Laplace operator involves coefficients a_{i,j}’s depending on the edge generating set K. Namely, the Laplace operator Δ satisfies

Δ = ∑_{i,j} a_{i,j} \frac{∂^{2}}{∂x_{i} ∂x_{j}}  (19)

= \frac{2d}{|K|} ∑_{g∈K^{∗}} \frac{∂^{2}}{∂g^{2}}

∼ −\frac{2d}{ϵ^{2}}L

Here we use K^{∗} to denote a subset of K so that at most one of a and a^{−1} is in K^{∗} for each a in K. The edge generators should be “evenly distributed” in the sense that the matrix (a_{i,j}) satisfies

C_{1}I ≤ (a_{i,j}) ≤ C_{2}I

for some constants C_{1} and C_{2} where I denotes the identity matrices. By choosing

c_{2} = \frac{2ϵ^{2}}{d}

we have

|c_{2}Δh + Lh| ≤ c_{2}ϵ^{4} \frac{d}{|K|} ∑_{g∈K} |\frac{∂^{4}}{∂g^{4}} h|

Note that in the Taylor series expansion, the \frac{∂^{3}}{∂g^{3}} terms cancel since the generators g and

g^{−1} are simultaneously in K. After substituting for \frac{∂^{4}}{∂g^{4}} h, we get

|c_{2}Δh + Lh| ≤ \frac{c_{2}c_{5}ϵ^{4}dh}{t^{2}}

where c_{5} depends on C_{1} and C_{2}.

For the general case of lattice graphs (without the condition that μ(x, gx) = ϵ for all vertex x and edge generator g), the Laplacian of the lattice graph is related to the Laplace-Beltrami operator as follows:

− \frac{2d}{ϵ^{2}}L ∼ \frac{2d}{|K|} ∑_{g∈K^{∗}}(\frac{ϵ}{μ(x, gx)})^{2} \frac{∂^{2}}{∂g^{2}}

= ∑_{i,j} a_{i,j} \frac{∂^{2}}{∂x_{i} ∂x_{j}}

where ϵ = min{μ(x, gx) : g ∈ K}. Then, we have

c_{5} ≤ min{C_{1}, C_{2}^{−1}}

Hence, we have

\frac{∂}{∂t}k(t, x) + Lk(t, x) ≤ \frac{c_{1} c_{5}ϵ^{4}d}{c_{2}t^{2}} ∫_{M} h(c_{2} t, x − z)φ(z)dz
= \frac{c_{5} ϵ^{4}d}{c_{2}t^{2}}k(t, x)

And,

\frac{∂}{∂t}k(t, x) + Lk(t, x) ≤ \frac{ϵ_{0}}{t^{2}} k(t, x)

where ϵ_{0} = \frac{c_{5}ϵ^{4}d}{c_{2}}.

To establish (B’) for ϵ′ ≤ c′d/log vol S and ϵ′′ = c′′/(volS |K|), we can choose c_{1} so that

k(ϵ′, x, x) = c_{1} ∫_{M} h(c_{2}ϵ′, x − z, x)φ(z)dz = 1

and for x ≠ y, we use the heat kernel estimates in Theorem 8 and 9 (proved later), to get

k(ϵ′, x, y) = c_{1} ∫_{M} h(c_{2}ϵ′, x − z, y)φ(z)dz
≤ exp(−\frac{ϵ^{2}}{4c_{2}ϵ′})k(ϵ′, x, x)
≤ \frac{c′′}{vol S}

We remark that we can make c′′ arbitrarily small by adjusting c′ in ϵ′.

To prove (C’) , we need to show that

| ∑_{\begin{matrix}x′ \\ \{x,x′\}∈S′ \end{matrix}} k(t, x, y) − k(t, x′, y)| ≤ \frac{ϵ_{1} |K| k(t, x, y)}{\sqrt{t}}

where ϵ_{1} = ϵd/\sqrt{c_{2}|K|}. The above inequality follows from that fact that |μ(x, x′)| = ϵ and the following estimate for the gradient of the heat kernel which will be proved later in the next section:

|∇h|(t, x, y) ≤ c_{6} \frac{d}{\sqrt{t}}h(t, x, y)

We consider

| ∑_{\begin{matrix}x′ \\ \{x,x′\}∈S′ \end{matrix}} k(t, x, y) − k(t, x′, y)|

≤ c_{1} | ∑_{\begin{matrix}x′ \\ \{x,x′\}∈S′ \end{matrix}} ∫ [h(c_{2}t, x, y − z) − h(c_{2}t, x′, y − z)]φ(z) dz|
≤ c_{1}ϵ\sqrt{d_{x}} ∫ |∇h|(c_{2}t, x, y − z)φ(z) dz
≤ c_{1}ϵ\sqrt{d_{x}} ∫ \frac{d}{\sqrt{c_{2}t}}h(c_{2}t, x, y − z)φ(z) dz
≤ \frac{ϵ\sqrt{d_{x}} d}{\sqrt{c_{2}t}}k(t, x, y)

Now, we need to estimate ∑_{z∈∂S} k(t − s, x, z)k(s, z, y). First we consider

|k(t, x, y) − U h(t, x, y)|
= |c_{1} ∫ h(c_{2}t, x, y − z)φ(z)dz − h(c_{2}t, x, y)c_{1} ∫ φ(z)dz|
≤ c_{1} ∫ |h(c_{2}t, x, y − z) − h(c_{2}t, x, y)|φ(z)dz
≤ c_{1} ∫ ϵ|∇h|(c_{2}t, x, y − z)φ(z)dz
≤ c_{1} ∫ \frac{ϵd}{\sqrt{c_{2}t}}h(c_{2}t, x, y − z)φ(z)dz
= \frac{ϵd}{\sqrt{c_{2}t}}k(t, x, y)

We will use the fact that |k(t, x, y) − U h(t, x, y)| is small when c_{2}t is large. Now we consider ∑_{z∈∂S} k(t − s, x, z)k(s, z, y) for a fixed s. Without loss of generality, we may assume that s ≤ t/2. We have

∑_{z∈∂S} k(t − s, x, z)k(s, z, y)

≤ ∑_{z∈∂S} Uh(c_{2}(t − s), x, z)c_{1} ∫ h(c_{2}s, z − z′, y)φ(z′)dz′ + l.o.t.
≤ c_{1}U ∫_{z′∈∪_{z∈∂S}U_{z}} h(c_{2}(t − s), x, z − z′)h(c_{2}s, z − z′, y)φ(z′)dz′ + l.o.t.
≤ U \frac{ϵ}{c_{2}t}h(c_{2}t, x, y) + l.o.t.
≤ \frac{ϵ}{c_{2}t}k(t, x, y) + l.o.t.

Here l.o.t. denotes a small fraction of the first term. From Theorem 5, we have

H_{t}(x, y) ≥ (1 − \frac{2c′ϵ_{1}}{\sqrt{t}})( min_{|t−s|≤ϵ′} k(s, x, y) − ϵ′′|K|)exp(−3ϵ_{0}/ϵ′)  (20)

where H is the heat kernel of the convex subgraph S.

In [9], Li and Yau proved the following lower bound for h.

Theorem [Li-Yau]: Let M denote a d-dimensional compact manifold with boundary ∂M. Suppose the Ricci curvature of M is nonnegative, and if ∂M ≠ ϕ, we assume that ∂M is convex. Then the fundamental solution of the heat equation with the Neumann boundary condition \frac{∂}{∂ν} u(t, x) = 0, satisfies

h(t, x, y) ≥ \frac{C}{B_{x}(\sqrt{t})}exp\frac{−μ^{2}(x, y)}{(4 − ϵ′)t}

for some constant C depending on d and ϵ′. Here, B_{x}(r) denotes the volume of the intersection of M and the ball of radius r centered at x.

However, the above version of the usual estimates for the heat kernel can not be directly used for our purposes here since the constant C is exponentially small depending on d. A more careful analysis of the heat kernel is needed. We will give a complete proof of the heat kernel estimates in a general terms in the next section. The proofs are partly based on the proofs in [9] and both the upper and lower bound estimates are given.

To lower-bound the discrete heat kernel, we will use the following lower bound estimates for the (continuous) heat kernel which will be proved later in Section 6. For any α > 0,

h(t, x, y) ≥ \frac{(1 + α)^{−d}}{4B_{x}(\sqrt{σ}t)}exp\frac{−(1 + α)μ^{2}(x, y)}{αt}  (21)

We choose

α = \frac{1}{d}
αc_{2}t_{0} = D^{2}(M)

where D(M) denotes the diameter of M. (We may assume D(M) ≥ 1). Therefore, by using (21) we have

h(c_{2}t_{0}, x, y) ≥ \frac{c_{7}}{vol M}

Also,

e^{−3ϵ_{0}/ϵ′} < const.

and

h(t_{1}, x, y) ≤ const. · h(t_{2}, x, y)

if t_{1} ≥ t_{0}/2 and |t_{1} − t_{2}| ≤ ϵ′. Using (20), we have

k(t_{0} − ϵ′, x, y) = c_{1} ∫_{M} h(c_{2} (t_{0} − ϵ′), x − z, y)φ(z)dz
≥ \frac{c_{1}c_{8}}{vol M} ∫_{M} φ(z)dz
≥ \frac{c_{8} U}{vol M}

where c’s denote some appropriate absolute constants. We then have

H_{t}(x, y) ≥ \frac{c_{9}U}{vol M}

From 1, we then have

λ ≥ \frac{∑_{x∈S} inf_{y∈S} H_{t}(x, y) exp(−3ϵ_{0}/ϵ′)}{2t}
≥ \frac{c_{9} U |S|}{t vol M}
≥ \frac{c_{9} ϵ^{2} r}{d^{2} D(M)^{2}}

where U denotes the volume of the Voronoi region and r denotes the ratio of U|S|/vol M. As a consequence, we have proved the following:

Theorem 6 Let S denote a convex subgraph of a simple lattice graph Γ and suppose S is embedded into a d-dimensional manifold M with a convex boundary and a distance function μ. Suppose for any edge {u, v} of S we have μ(u, v) = ϵ. Then the Neumann eigenvalue λ of S satisfies the following inequality:

λ ≥ \frac{c_{0} r ϵ^{2}}{d^{2}D(M)^{2}}

where c_{0} is an absolute constant (depending only on Γ and is independent of S), K is the set of edge generators of the lattice graph,

r = \frac{U |S|}{vol M}

and U denotes the volume of the Voronoi region.

To get a simpler lower bound for λ, we note that the diameter D(S) of the convex subgraph S and the diameter of the manifold are related by

D(M) ≤ ϵ D(S)  (22)

Therefore, we have the following:

Corollary 1 Let S denote a convex subgraph of a simple lattice graph and suppose S is embedded into a d-dimensional manifold M with a convex boundary. Then the Neumann eigenvalue λ_{S} of S satisfies the following inequality:

λ ≥ \frac{c_{0} r}{d^{2}D^{2}(S)}

where

r = \frac{U |S|}{vol M} ,

D(S) denotes the (graph) diameter of S, K denotes the set of edge generators and c_{0} is an absolute constant depending only on the simple Lattice graph.

For the general case of the lattice graphs, we have the following:

Theorem 7 Let S denote a convex subgraph of a lattice graph and suppose S is embedded into a d-dimensional manifold M with a convex boundary and a distance function μ. Let K denote the set of edge generators and suppose ϵ = min{μ(x, gx) : g ∈ K}. Assume that

−\frac{2d}{ϵ^{2}}L ∼ \frac{2d}{|K|} ∑_{g∈K^{∗}}(\frac{ϵ}{μ(x, gx)})^{2} \frac{∂^{2}}{∂g^{2}}

= ∑_{i,j} a_{i,j} \frac{∂^{2}}{∂x_{i} ∂x_{j}}

and

C_{1}I ≤ (a_{i,j}) ≤ C_{2}I

where I is the identity matrix.

c_{5} ≤ min{C_{1}, C_{2}^{−1}}

Then the Neumann eigenvalue λ of S satisfies the following inequality:

λ ≥ \frac{c_{0} r ϵ^{2}}{d^{2}D(M)^{2}}

where

r = \frac{U |S|}{vol M}

U denotes the volume of the Voronoi region, and c_{0} is an absolute constant satisfying

c_{0} ≤ C_{0} min{C_{1}, C_{2}^{−1}}

for an absolute constant C_{0}.

Remark 2: The constant C_{0} can be roughly estimated with a value of 1/100.

Remark 3: For a polytope in ℝ^{d}, we can rescale and choose the lattice points to be dense enough to approximate the volume of the polytope. For example, if we have

C ϵ ≤ D_{1}(M)/d  (23)

where D_{1} denote the diameter of M measured by the L_{1} norm and C is some absolute constant, then the number of lattice points provides a good approximation for the volume of the polytope. This implies that r ≥ c for some constant c. The above inequality (23) can be replaced by a slightly simpler inequality:

C d ≤ D(S)

for some constant C. These facts are useful for approximation algorithms for the volume of a convex body which will be discussed in the next section.

Remark 4: There are many graphs G that can be embedded in a lattice graph such that the diameter of G satisfies

D(G) ∼ \frac{\sqrt{d} D(M)}{ϵ}

For such graphs, Theorem 6 implies a somewhat stronger result:

λ ≥ \frac{c_{0}r}{d^{2}D(G)^{2}}

where r is as defined in Theorem 6.

9 Estimates for the continuous heat kernel

In this section, we will analyze the (continuous ) heat kernel. We remark that there is a large literature on the estimates of the heat kernel. However, in such estimates, the dimension d is usually taken as a constant and the approximations are often crude. Here, we will give upper and lower bound estimates which are quite sharp in a general setting. The methods here are partly based on the proofs in [9]. It is anticipated that these estimates can be useful for many other problems as well. We will first prove an upper bound for the heat kernel. This bound will be used later for establishing the lower bounds.

Throughout this section, we use the following notation:

Let M denote a d-dimensional compact manifold with boundary ∂M. Suppose the Ricci curvature of M is nonnegative, and if ∂M ≠ ϕ, we assume that ∂M is convex. The fundamental solution h of the heat equation satisfies the Neumann boundary condition \frac{∂}{∂ν} u(t, x) = 0 for x ∈ ∂M.

Theorem 8 For any α > 0 and t > 0,

h(t, x, y) ≤ (1 + α)^{d} B_{x}^{−1/2}(\sqrt{α(2 + α)t}) B_{y}^{−1/2}(\sqrt{αt})

exp\frac{−μ^{2}(x, y)}{4(1 + 2α)(1 + α)^{2}t} exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)})

Proof: We follow from the proof of Theorem 3.1 on p. 175 of [9] with the value for α, τ and θ in [9] to be α = 1, τ = 0, θ = 0, in order to derive the following inequality:

h(t, x, y) ≤ (1 + α)^{d} B^{−1/2}(S_{1}) B^{−1/2}(S_{2}) exp (2 ρ̃(x, S_{2}, α(1 + α)t))
exp (ρ̃(y, S_{1}, αt)) exp (\underline{ρ}(x, S_{1}, (1 + 2α)(1 + α)t))

Here we choose S_{1} and S_{2} as follows:

S_{1} = B_{y}(\sqrt{αt}), S_{2} = B_{x}(\sqrt{α(2 + α)t})

Then

2 ρ̃(y, S_{2}, α(2 + α)t) ≤ \frac{1}{2}

ρ̃(x, S_{1}, αt)) ≤ \frac{1}{4}

We define W to be

W = \underline{ρ}(x, S_{1}, (1 + 2α)(1 + α)t) = inf_{x∈B_{y}(\sqrt{αt})} \frac{μ^{2}(x, z)}{4(1 + 2α)(1 + α)t}

If x ∈ B_{y}(\sqrt{αt}), then we have

W = 0 ≥ \frac{μ^{2}(x, z)}{4(1 + 2α)(1 + α)^{2}t} − \frac{α}{4(1 + 2α)(1 + α)^{2}}

If x ∉ B_{y}(\sqrt{αt}), then μ(x, y) ≥ \sqrt{αt} and

W ≥ \frac{(μ(x, y) − \sqrt{αt})^{2}}{4(1 + 2α)(1 + α)t}

Since

(μ(x, y) − \sqrt{αt})^{2} ≥ \frac{μ^{2}(x, y)}{1 + α} − t

we have

W ≥ \frac{μ(x, y)^{2}}{4(1 + 2α)(1 + α)^{2}t} − \frac{1}{4(1 + 2α)(1 + α)}

Therefore, from Theorem 3.1 (ii) in [9], we have

h(t, x, y) ≤ (1 + α)^{d} B_{x}^{−1/2}(\sqrt{α(2 + α)t}) B_{y}^{−1/2}(\sqrt{αt})

exp\frac{−μ^{2}(x, y)}{4(1 + 2α)(1 + α)^{2}t} exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)})

as claimed.

Before proceeding to prove the lower bound, we need the following assumption:

c_{11}^{−1}B_{y}(\sqrt{αt}) ≤ B_{x}(\sqrt{αt}) ≤ c_{11}B_{y}(\sqrt{αt})  (24)

for some constant c_{11}. We note that the above assumption holds for c_{11} = 1 if αt is larger than the square of the diameter of M.

Theorem 9 For any α > 0, t ≥ 0, and σ satisfying σ ≥ cdα,

h(t, x, y) ≥ \frac{(1 + α)^{−d/2}}{4B_{x}(\sqrt{\frac{σt}{2}})} exp(\frac{−(1 + α)μ^{2}(x, y)}{4αt})

provided (24) holds.

Proof: Using (24), we have

h(t, x, y) ≤ c_{11}^{−1/2}(1 + α)^{d} B_{x}^{−1/2}(\sqrt{α(2 + α)t}) B_{x}^{−1/2}(\sqrt{αt})

exp\frac{−μ^{2}(x, y)}{4(1 + 2α)(1 + α)^{2}t} exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)})

Since

∫ h(t, x, y)dy = 1,

we have

1 ≤ ∫_{μ(x,y)≤\sqrt{σt}} h(t, x, y)dy

+c_{11}^{−1/2}(1 + α)^{d} B_{x}^{−1/2}(\sqrt{α(2 + α)t}) B_{x}^{−1/2}(\sqrt{αt})

exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)}) ∫_{μ(x,y)≥\sqrt{σt}} exp\frac{−μ^{2}(x, y)}{4(1 + 2α)(1 + α)^{2}t}dy

≤ ∫_{μ(x,y)≤\sqrt{σt}} h(t, x, y)dy

+c_{11}^{−1/2}(1 + α)^{d} B_{x}^{−1/2}(\sqrt{α(2 + α)t}) B_{x}^{−1/2}(\sqrt{αt})

exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)}) ∫_{√\overline{σt}}^{∞} exp\frac{−r^{2}}{4(1 + 2α)(1 + α)^{2}t}dB(r)

Assume for r_{2} ≥ r_{1}, the following holds:

\frac{B(r_{2})}{B(r_{1})} ≤ \frac{r_{2}}{r_{1}}

we obtain

∫_{√\overline{σt}}^{∞} exp\frac{−r^{2}}{4(1 + 2α)(1 + α)^{2}t}dB(r)

≤ \frac{1}{2(1 + 2α)(1 + α)^{2}} ∫_{√\overline{σt}}^{∞} exp\frac{−r^{2}}{4(1 + 2α)(1 + α)^{2}t} \frac{r B(r)}{t}d r
≤ \frac{B(\sqrt{αt})}{2(1 + 2α)(1 + α)^{2}\sqrt{α}} ∫_{√\overline{σt}}^{∞} exp\frac{−r^{2}}{4(1 + 2α)(1 + α)^{2}t} \frac{r^{2}}{t\sqrt{t}}d r
≤ \frac{B(\sqrt{αt})}{4(1 + 2α)(1 + α)^{2}\sqrt{α}} ∫_{√\overline{σt}}^{∞} exp\frac{−r^{2}}{4(1 + 2α)(1 + α)^{2}t} \frac{r}{\sqrt{t}}d \frac{r^{2}}{t}
≤ \frac{2B(\sqrt{αt})\sqrt{1 + 2α}(1 + α)}{\sqrt{α}} ∫ ∞_{\frac{σ}{4(1+2α)(1+α)^{2}}} exp(−τ)\sqrt{τ}d τ

Therefore we have

c_{11}^{−1/2}(1 + α)^{d} B_{x}^{−1/2}(\sqrt{α(2 + α)t}) B_{x}^{−1/2}(\sqrt{αt})

exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)}) ∫_{√\overline{σt}}^{∞} exp\frac{−r^{2}}{4(1 + 2α)(1 + α)^{2}t}dB(r)

≤ c_{11}^{−1/2} \frac{(1 + α)^{d+1}\sqrt{1 + 2α}}{\sqrt{α}}

exp(\frac{3}{4} + \frac{1}{4(1 + 2α)(1 + α)}) ∫ ∞_{\frac{σ}{4(1+2α)(1+α)^{2}}} exp(−τ)\sqrt{τ}d τ

We choose σ > cdα so that the above term is no more than 1/2. Hence

∫_{μ(x,y)≤\sqrt{σt}} h(t, x, y) ≥ \frac{1}{2}

But

h(2t, x, x) = ∫_{M} h^{2}(t, x, y).

Hence

h(2t, x, x) ≥ ∫_{μ(x,y)≤\sqrt{σt}} h^{2}(t, x, y)
≥ B_{x}^{−1}(\sqrt{σt})(∫_{μ(x,y)≤\sqrt{σt}} h(t, x, y))^{2}
≥ \frac{1}{4B_{x}(\sqrt{σt})}

This implies

h(t, x, x) ≥ \frac{1}{4B_{x}(\sqrt{\frac{σt}{2}})}

By the Harnack inequality in Theorem 2.3 in [9], we have

h(t_{1}, x, x) ≤ h(t_{2}, x, y)(\frac{t_{2}}{t_{1}} )^{d/2} exp(\frac{μ^{2}(x, y)}{4(t_{2} − t_{1})})  (25)

for t_{2} > t_{1}. Hence for any α > 0, we have

h(t, x, y) ≥ h(\frac{t}{1 + α}, x, x)(1 + α)^{−d/2} exp(\frac{−(1 + α)μ^{2}(x, y)}{4αt})
≥ \frac{(1 + α)^{−d/2}}{4B_{x}(\sqrt{\frac{σt}{2}})} exp(\frac{−(1 + α)μ^{2}(x, y)}{4αt})

This completes the proof of Theorem 9.

We will also need estimates for the gradient of h. First, we will prove a useful Fact.

Theorem 10 For any r > 0 and σ > 0, we have

∫_{B_{y}(r)} |∇h|^{2}(t, x, z)dz ≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t}) ∫_{B_{y}((1+σ)r)} h^{2}(t, x, z)dz

Proof: We start with the following inequality which was established on page 163, as Theorem 1.3 of [9] (for the special case of τ = 0 = θ = q).

|∇h|^{2} ≤ h h_{t} + \frac{d}{2t}h^{2}

Therefore we have

∫ ρ^{2}(z)|∇h|^{2}(t, x, z)dz ≤ ∫ ρ^{2}(z)h(t, x, z)h_{t}(t, x, z)dz + \frac{d}{2t} ∫ ρ^{2}(z)h^{2}(t, x, z)dz
= ∫ ρ^{2}(z)h(t, x, z)Δh(t, x, z)dz + \frac{d}{2t} ∫ ρ^{2}(z)h^{2}(t, x, z)dz

Here we define

ρ(z) = \{ \begin{matrix}1 & if μ(y, z) ≤ r \\ 0 & if μ(y, z) ≥ (1 + σ)r \end{matrix}

and

|∇ρ| ≤ \frac{1}{σr}

We note that

∫ ρ^{2}(z)h(t, x, z)Δh(t, x, z)dz
= − ∫ ρ^{2}(z)|∇h|^{2}(t, x, z)dz − 2 ∫ ρ(z)h(t, x, z)∇ρ(z)∇h(t, x, z)dz
= ∫ |∇ρ|^{2}h^{2}(t, x, z)dz

Hence, we have

∫ ρ^{2}(z)|∇h|^{2}(t, x, z)dz ≤ ∫ (|∇ρ|^{2} + \frac{d}{2t}ρ^{2})h^{2}(t, x, z)dz

Therefore,

∫_{B_{y}(r)} |∇h|^{2}(t, x, z)dz ≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t}) ∫_{B_{y}((1+σ)r)} h^{2}(t, x, z)dz

Theorem 11 For σ > 0, α > 0,

|∇h|(t, x, y) ≤ 3(1 + α)^{2d}(\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})^{1/2}h((1 + α)t, x, y)

if r^{2} ≤ α^{2}t and α < 1/d. Proof: For a fixed x, we consider f(t, y) = |∇h|(t, x, y). Let ρ be defined as in Theorem 9.

We have

f(t, y) − ∫ f(t_{1}, z)h(t − t_{1}, z, y)ρ(z)dz

= ∫_{t_{1}}^{t} \frac{∂}{∂s} ∫ f(s, z)h(t − s, z, y)ρ(z) dz ds
= ∫_{t_{1}}^{t} ∫ [Δf(s, z)h(t − s, z, y)ρ(z) − f(s, z)(Δh)(t − s, z, y)ρ(z)] dz ds
= ∫_{t_{1}}^{t} ∫ [f(s, z)Δ(h(t − s, z, y)ρ(z)) − f(s, z)(Δh)(t − s, z, y)ρ(z)] dz ds
= ∫_{t_{1}}^{t} ∫ f(s, z)[2∇h(t − s, z, y)∇ρ(z)) + h(t − s, z, y)∇ρ(z)] dz ds
= ∫_{t_{1}}^{t}[\frac{1}{σr} ∫_{B_{y}((1+σ)r)} 2f(s, z)∇h(t − s, z, y) + \frac{1}{σ^{2}r^{2}} ∫_{B_{y}((1+σ)r)} f(s, z)h(t − s, z, y)] dz ds

To complete the proof, it suffices to establish upper bounds of

(1 + α)^{2d}(\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})^{1/2}h((1 + α)t, x, y)

for the following three items separately, under the assumption that t − t_{1} = αt.

(a) ∫_{B_{y}((1+σ)r)} f(t_{1}, z)h(t − t_{1}, z, y) dz,

(b) ∫_{t_{1}}^{t} \frac{1}{σr} ∫_{B_{y}((1+σ)r)} f(s, z)∇h(t − s, z, y) dz ds

(c) ∫_{t_{1}}^{t} \frac{1}{σ^{2}r^{2}} ∫_{B_{y}((1+σ)r)} f(s, z)h(t − s, z, y)] dz ds

First, we consider (a)

(∫_{B_{y}((1+σ)r)} f(t_{1}, z)h(t − t_{1}, z, y)dz)^{2}
≤ ∫_{B_{y}((1+σ)r)} f^{2}(t_{1}, z) dz ∫_{B_{y}((1+σ)r)} h^{2}(t − t_{1}, z, y) dz
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t}) ∫_{B_{y}((1+σ)r)} h^{2}(t_{1}, x, z) dz h(2(t − t_{1}), y, y)
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})(1 + α)^{d}h^{2}((1 + α)t_{1}, x, y) ∫_{B_{y}((1+σ)r)} exp \frac{(1 + σ)μ(y, z)^{2}}{2tα} dz h(2(t − t_{1}), y, y)

Here we use the Harnack inequality (25) for upper bounding h(s, x, z). Using the assumption that

r^{2} ≤ α(t − t_{1})

we have

(∫_{B_{y}((1+σ)r)} f(t_{1}, z)h(t − t_{1}, z, y)dz)^{2}
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})(1 + α)^{d}h^{2}((1 + α)t_{1}, x, y)B_{y}((1 + σ)r)h(2(t − t_{1}), y, y)
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})(1 + α)^{d}h^{2}((1 + α)t_{1}, x, y)B_{y}((1 + σ)r)(1 + α)^{d/2} \frac{1}{B_{y}(\sqrt{2α(t − t_{1})})}
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})(1 + α)^{2d}h^{2}((1 + α)t_{1}, x, y)

Therefore we have

∫_{B_{y}((1+σ)r)} f(t_{1}, z)h(t − t_{1}, z, y)dz
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})^{1/2}(1 + α)^{d}h((1 + α)t_{1}, x, y)
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})^{1/2}(1 + α)^{2d}h((1 + α)t, x, y)

To bound (b), we have

∫_{t_{1}}^{t} \frac{1}{σr} ∫_{B_{y}((1+σ)r)} f(s, z)∇h(t − s, z, y) dz ds

≤ \frac{(t − t_{1})^{1/2}}{σr} (∫_{B_{y}((1+σ)r)} f^{2}(s_{0}, z) dz)^{1/2} (∫_{t_{1}}^{t} ∫_{B_{y}((1+σ)r)} ∇h^{2}(t − s, z, y) dz ds)^{1/2}
≤ \frac{(t − t_{1})^{1/2}}{σr} (\frac{1}{σ^{2}r^{2}} + \frac{2d}{t})^{1/2}h((1 + α)s_{0}, x, y) B_{y}((1 + σ)r)

(∫_{t_{1}}^{t} ∫_{B_{y}((1+σ)r)} ∇h^{2}(t − s, z, y) dz ds)^{1/2}

It can be checked that

∫_{t_{1}}^{t} ∫_{B_{y}((1+σ)r)} ∇h^{2}(t − s, z, y) dz ds

≤ ∫_{t_{1}}^{t} ∫_{B_{y}((1+σ)r)}(\frac{1}{σ^{2}r^{2}} + \frac{d}{t − s})h^{2}(t − s, z, y) dz ds

≤ ∫_{0}^{(1+σ)r} ∫_{t_{1}}^{t}(\frac{1}{σ^{2}r^{2}} + \frac{d}{t − s})\frac{(1 + α)^{d} exp \frac{−q^{2}}{2α(t−s)}}{B_{y}^{2}(\sqrt{α(t − s)})} ds d B_{y}(q)

≤ ∫_{0}^{(1+σ)r}(1 + α)^{d}(\frac{1}{ασ^{2}r^{2}} \frac{q^{n−3}}{(α(t − t_{0}))^{n−2}} + \frac{1}{α} \frac{q^{n−3}}{(α(t − t_{0}))^{n−3}} ) dq
≤ (1 + α)^{d} \frac{1}{ασ^{2}r^{2}} \frac{1}{(α(t − t_{0}))^{n/2−1}}

Since t − t_{1} = αt, r^{2} < α^{2}t we have

∫_{t_{1}}^{t} \frac{1}{σr} ∫_{B_{y}((1+σ)r)} f(s, z)∇h(t − s, z, y) dz ds

≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})^{1/2}(1 + α)^{d}h((1 + α)t_{1}, x, y)
≤ (\frac{1}{σ^{2}r^{2}} + \frac{d}{2t})^{1/2}(1 + α)^{2d}h((1 + α)t, x, y)

Very similar arguments are used for upper bounding (c):

∫_{t_{1}}^{t} \frac{1}{σ^{2}r^{2}} ∫_{B_{y}((1+σ)r)} f(s, z)h(t − s, z, y) dz ds

≤ \frac{(t − t_{1})^{1/2}}{σ^{2}r^{2}} (∫_{B_{y}((1+σ)r)} f^{2}(s_{0}, z) dz)^{1/2}(∫_{t_{1}}^{t} ∫_{B_{y}((1+σ)r)} h(t − s, z, y) dz ds)^{1/2}
≤ (\frac{1}{σ^{2}r^{2}} + \frac{2d}{t})^{1/2}(1 + α)^{2d}h((1 + α)t, x, y)

As a corollary of Theorem 11, by choosing α = \frac{1}{d} and r^{2} = α^{2}t, we have

Corollary 2

|∇h|(t, x, y) ≤ c\frac{d}{t^{1/2}} h(t, x, y)

for some constant c.

10 Neumann eigenvalues and random walks

This section consists of four subsections: First, we give a brief discussion on random walks and, especially, on the associated weighted graphs. Then, we generalize the Laplacian, and heat kernels for weighted graphs and induced subgraphs. All results in previous sections can be extended to the weighted graphs. Finally, we will illustrate the relationship between the eigenvalues of the Laplacian and the rate of convergence of the corresponding random walk.

10.1 Random walks on graphs

In a graph G, a walk is just a sequence of vertices (v_{0}, v_{1}, ⋯, v_{s}) with {v_{i−1}, v_{i}} ∈ E(G), for 1 ≤ i ≤ s. A random walk is determined by the transition probability π(u, v) = P rob(x_{i+1} = v|x_{i} = u) which is independent of i. Clearly, for each vertex u

∑_{v} π(u, v) = 1

For any initial distribution f : V → ℝ with ∑_{v} f(v) = 1, the distribution after k steps is

just fP^{k} (in the notation of matrix multiplication by viewing f as a row vector where P is the matrix of transition probability). The random walk is said to be ergodic if there is a stationary distribution π(v) satisfying

lim_{s→∞} fP^{s}(v) = π(v)

Necessary and sufficient conditions for ergodicity are (i) irreducible, i.e., for any u, v ∈ V, there exists some s such that P^{s}(u, v) > 0; (ii) aperiodic, i.e., gcd {s : P^{s}(u, v) > 0} = 1. The problem of interest is to determine, from any initial distribution, the number of steps s required for P^{s} to be close to its stationary distribution.

In particular, we say the ergodic random walk is reversible if

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

An alternative description for a reversible random walk is given by considering a weighted connected graph with edge weights

w(u, v) = w(v, u) = π(v)π(v, u)/c

where c is the average of π(v)π(v, u) over all (v, u) with π(v, u) ≠ 0. A random walk in a weighted graph has as transition probability

π(u, v) = \frac{w(u, v)}{d_{u}}

where d_{u} = ∑_{z} w(u, z) is the (weighted) degree of u. The two conditions for ergodicity are equivalent to (1) connectivity and (ii) that the graph is not bipartite. We remark that an unweighted graph has w(u, v) either 0 or 1. A typical random walk has transition probability 1/d_{v} of moving from a vertex v to one of its neighbors. The transition matrix P = (π(u, v)) satisfies

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

for any f : V (G) → ℝ. In other words,

P (u, v) = \{ \begin{matrix}1/d_{u} & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

It is easy to check that

P = T^{−1}A = T^{−1/2}(I − L)T^{1/2}.

where A is the adjacency matrix.

For an induced subgraph S of a graph G, we consider the following random walk: The probability of moving from a vertex v in S to a neighbor u of v is 1/d_{v} if u is in S. If u is not in S, we then move from v to each neighbor of u in S with the (additional) probability 1/d_{v}d′_{u} where d′_{u} denotes the number of neighbors of u in S. The transition matrix P for this walk, whose columns and rows are indexed by S, is defined as follows:

fP (v) = ∑_{\begin{matrix}u∈S \\ u∼v \end{matrix}} \frac{1}{d_{u}} f(u) + ∑_{\begin{matrix}u∈S \\ u∼z∼v \\ z∉S \end{matrix}} \frac{1}{d_{u}d′_{z}} f(u)  (26)

The stationary distribution is d_{v}/ ∑_{u} d_{u} at a vertex v. The eigenvalues ρ_{i} of P are closely

related to the Neumann eigenvalues λ_{S,i} as follows:

ρ_{i} = 1 − λ_{S,i}

In particular, we have

ρ = ρ_{1} = 1 − λ_{S,1} = 1 − λ_{S}  (27)

This can be proved by using the Neumann condition as follows:

1 − ρ = inf_{f} \frac{∑_{\begin{matrix}x∼y \\ x,y∈S \end{matrix}}(f(x) − f(y))^{2} + ∑_{\begin{matrix}x∼z∼y \\ x,y∈S,z∉S \end{matrix}}(f(x) − f(y))^{2}/d_{z}}{∑_{x∈S} f^{2}(x)d_{x}}

≥ inf_{f} \frac{∑_{\begin{matrix}x∼y \\ x,y∈S \end{matrix}}(f(x) − f(y))^{2} + ∑_{z∉S} ∑_{\begin{matrix}x∼z \\ x∈S \end{matrix}}[d′_{z}f^{2}(x) − (∑_{\begin{matrix}y∼z \\ y∈S \end{matrix}} f(y))^{2}]/d′_{z}}{∑_{x∈S} f^{2}(x)d_{x}}

≥ inf_{f} \frac{∑_{\begin{matrix}x∼y \\ x,y∈S \end{matrix}}(f(x) − f(y))^{2} + ∑_{z∉S} ∑_{\begin{matrix}x∼z \\ x∈S \end{matrix}}(f^{2}(x) − f^{2}(z))}{∑_{x∈S} f^{2}(x)d_{x}}

≥ inf_{f} \frac{∑_{\begin{matrix}x∼y \\ x,y∈S \end{matrix}}(f(x) − f(y))^{2} + ∑_{z∉S} ∑_{\begin{matrix}x∼z \\ x∈S \end{matrix}}(f(x) − f(z))^{2}}{∑_{x∈S} f^{2}(x)d_{x}}

= inf_{f} \frac{∑_{\{x,y\}∈Ŝ}(f(x) − f(y))^{2}}{∑_{x∈S} f^{2}(x)d_{x}}

= λ_{S}

where f ranges over all functions f : δS ∪ S → ℝ satisfying

∑_{x∈S} f(x) = 0

and for x ∈ δS

∑_{y∈S,y∼x}(f(x) − f(y)) = 0

The inequality (27) is quite useful in bounding the rate of convergence of random walks and the rapid mixing of markov chains.

Suppose S is an induced subgraph of a k-regular graph. The above random walk can be described as follows: At an interior vertex v of S, the probability of moving to each neighbor is equal to 1/k. (An interior vertex of S is a vertex not adjacent to any vertex not in S.) At a boundary vertex of v ∈ δS, the probability of moving to a neighbor u of v is 1/k unless u is not in S and, in this case, the (additional) probability of 1/(kd′_{u}) is assigned for moving from v to each neighbor of u in S. The stationary distribution of the above random walk is just the uniform distribution.

For the general case for random walks, we need to generalize the definitions for Laplacian and heat kernels to weighted graphs and subgraphs.

10.2 Eigenvalues for weighted graphs and subgraphs

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

w(u, v) = w(v, u)

and

w(u, v) ≥ 0.

We note that if {u, v} ∉ E(G) , then w(u, v) = 0. Also w(v, v) can be positive. For unweighted graphs, they are just the special case of taking the weights to be 0 or 1.

The degree d_{v} of a vertex v is just:

d_{v} = ∑_{u} w(u, v).

We generalize the definitions of previous sections so that

L(u, v) = \{ \begin{matrix}d_{v} − w(v, v) & if u = v, \\ −w(u, v) & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

In particular, for a function f : V → ℝ, we have

Lf(x) = ∑_{\begin{matrix}y \\ \{x,y\}∈S′ \end{matrix}}(f(x) − f(y))w(x, y)

Let T denote the diagonal matrix with the (v, v)-th entry having value d_{v}. The Laplacian of G is defined to be

L = T^{−1/2}LT^{−1/2}.

In other words, we have

L(u, v) = \{ \begin{matrix}1 − \frac{w(v, v)}{d_{v}} & if u = v, \\ −\frac{w(u, v)}{\sqrt{d_{u}d_{v}}} & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

Therefore, by using the generalized version of L and L, the previous definitions for the eigenvalues for an induced subgraph S can still be utilized:

λ_{S} = inf_{\begin{matrix}f \\ ∑ f(x)d_{x}=0 \end{matrix}} \frac{∑_{\{x,y\}∈S′}(f(x) − f(y))^{2}w(u, v)}{∑_{x∈S} f^{2}(x)d_{x}}  (28)

= inf_{\begin{matrix}f \\ ∑ f(x)d_{x}=0 \end{matrix}} \frac{∑_{x∈S} f(x)Lf(x)}{∑_{x∈S} f^{2}(x)d_{x}}

= inf_{g⊥T^{1/2}1} \frac{⟨g, Lg⟩_{S}}{⟨g, g⟩_{S}}

The Neumann condition is then

∑_{\begin{matrix}y \\ \{x,y\}∈∂S \end{matrix}}(f(x) − f(y))w(x, y) = 0

for x ∈ δS. We can define the heat kernel for weighted graphs in the same way as in Section 4. All the proofs in previous sections work in similar fashion and we obtain the same eigenvalue inequalities for weighted graphs:

Theorem 12 In a graph with edge weights w(x, y), for t > 0, we have

λ_{S} ≥ \frac{1}{2t} ∑_{x∈S} inf_{y∈S} \frac{H_{t}(x, y)\sqrt{d_{x}}}{\sqrt{d_{y}}}  (29)

10.3 Eigenvalues and the rate of convergence

In a random walk with the associated weighted connected graph G, the transition matrix P satisfies

1T P = P T 1 = T 1

and therefore the stationary distribution is exactly T 1/volG where vol(G) = ∑_{x} d_{x}. We want to show that when k is large enough, for any initial distribution f : V → ℝ, fP^{k} converges to the stationary distribution ϕ_{0} = T 1/vol(G). Suppose we write

fT^{−1/2} = ∑_{i} a_{i}ϕ_{i}

where ϕ_{i} denotes the eigenfunction associated with λ_{i}.

We have

∥fP^{s} − a_{0}ϕ_{0} ∥ = ∥fT^{−1/2}(I − L)^{s}T^{1/2} − T 1/vol G ∥
= ∥ ∑_{i≠0}(1 − λ_{i})^{s}a_{i}ϕ_{i}T^{1/2}∥
≤ (1 − λ)^{s} ∥f∥
≤ e^{−sλ}

where λ = λ_{1} if 1 − λ_{1} ≥ λ_{n−1} − 1 and λ = 2 − λ_{n−1}, otherwise.

So, after s ≥ (1/λ) log(1/ϵ) steps, the L_{2} distance between fP^{s} and its stationary distribution is less than ϵ.

Although λ occurs in the above upper bound for the distance between the stationary distribution and the s-step distribution, in fact, only λ_{1} is crucial in the following sense. Note that λ is either λ_{1} or 2 − λ_{n−1}. Suppose the latter holds (when λ_{n−1} − 1 ≥ 1 − λ_{1}). We can consider a modified random walk on the graph G′ formed by adding d_{v} loops to each vertex v. The new graph has Laplacian λ′_{k} = λ_{k}/2 ≤ 1 which follows from equation (28). Therefore,

1 − λ′_{1} ≥ 1 − λ′_{n−1} ≥ 0

The convergence bound for the modified random walk becomes (2/λ_{1}) log(1/ϵ).

A stronger notion of convergence is measured by L_{1} or the relative pointwise distance which is defined as follows (also see [12]): After s steps, the relative pointwise distance (r.p.d.) of P to the stationary distribution π(x) is given by

Δ(s) = max_{x,y} \frac{|P^{s}(y, x) − π(x)|}{π(x)}

It is not difficult to show [6] that

Δ(t) ≤ e^{−sλ_{1}/2} \frac{vol G}{min_{x} d_{x}}

So, if we choose t such that

s ≥ \frac{2}{λ_{1}} log \frac{vol G}{ϵ min_{x} d_{x}}

then after s steps, we have Δ(s) ≤ ϵ.

10.4 Applications on random walks and rapidly mixing Markov chains

Many combinatorial and computational problems involve enumerating families of combinatorial objects. Such enumeration problems are often difficult and are widely believed to be computationally intractable (e. g., the class of the so-called #P-complete problems [14]). An alternative approach is to consider approximation algorithms. In this direction, there has been a great deal of progress in recent years in developing efficient approximation algorithms by using sampling algorithms. Roughly speaking, if we can generate a “random” member of the family in polynomial time, then a polynomial approximation algorithm for the enumeration problem can be obtained, provided that certain technical conditions are satisfied (see [12]).

A sampling algorithm can often be described in terms of a random walk on a graph. Namely, the vertex set of the graph consists of the combinatorial objects which we wish to sample. The edges are usually determined by some “local ” rules. For example, from each vertex, we define its neighboring vertices by choosing some simple transformations of the object. The random walk can then be described by its transition matrix P where P (u, v) denotes the probability of moving from vertex u to its neighbor v at each step. The problem of interest is to determine how many steps are required to move from a starting vertex to eventually reach a “random” vertex. In other words, how fast can an initial distribution converge to the stationary distribution by repeatedly applying the transition rules? A good bound of the rate of convergence often leads to polynomial approximation algorithms for the original enumeration problem.

To demonstrate the use of Theorem 6, we consider a classical problem of computing the volume of a convex body in d-dimensional Euclidean space. Although this problem is known to be computationally difficult, there have been a great deal of progress in obtaining randomized approximation algorithms based on the first polynomial time (O(d^{27})) algorithm by Dyer, Frieze and Kannan [8] (also see [11]). The main part of the algorithm is basically a random walk problem on the lattice points inside of the convex body. There have been a series of papers improving the volume algorithms with complexity lowered to O(n^{5}logn) [10]. The eigenvalue inequality of Theorem 5 provides a more direct way of bounding the eigenvalues and the rate of convergence of the random walks.

Another example is the problem of random walks on matrices with non-negative integral entries having given row and column sums, arising in connection with exact inferences of contingency tables and their probability distributions (see [1, 7]). This problem can be reduced to a problem of bounding eigenvalues of convex subgraphs of the homogeneous graphs as described in Example 1. The diameter of the convex subgraph for contingency tables with given row and column sums can be easily evaluated and is bounded above by the sum of all column sums minus the maximum column sum. Using Theorem 6, for n × n tables with column and row sums equal to s, the eigenvalue λ can be upper-bounded by \frac{c}{n^{3}s^{2}} , provided s is at least cn^{2}. Therefore, a random walk on the subgraph converges in cn^{3}s^{2} steps. More details on the contingency table problem can be found in [5].

In a subsequent paper [5], a variety of sampling and enumeration problems will be examined. By using the eigenvalue inequality established in Theorem 6, the upper bound for the convergence of the random walks on the corresponding convex subgraphs can often be improved by a factor of a power of n which then sometimes can lead to a better approximation algorithm.

Acknowledgement The authors wish to thank Peter Li for numerous stimulating discussions which were instrumental in the preparation of this paper.

References

[1] Y. Bishop, S. Fienberg, P. Holland, Discrete Multivariate Analysis, MIT Press, Cambridge, 1975.

[2] Siu Yuen Cheng, Peter Li and Shing-Tung Yau, On the upper estimate of the heat kernel of a complete Riemannian manifold, American Journal of Mathematics 103 (1981), 1021-1063.

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

[4] F. R. K. Chung and S. -T. Yau, The heat kernels for graphs and induced subgraphs, preprint.

[5] F. R. K. Chung, R. L. Graham and S. -T. Yau, On sampling with Markov chains.

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

[7] Persi Diaconis and Bernd Sturmfels, Algebraic Algorithms for Sampling from Conditional Distributions, preprint

[8] M. Dyer, A. Frieze and R. Kannan, A random polynomial time algorithm for approximating the volume of convex bodies, JACM, 38 (1991) 1-17

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

[10] L. Lovász, personal communication.

[11] L. Lovász and M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Structures and Algorithms, 4 (1993) 359-412

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

[13] A.J. Sinclair and M.R. Jerrum, Approximate counting, uniform generation, and rapidly mixing markov chains, Information and Computation, 82 (1989) 93-133

[14] L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci.8 (1979) 189-201

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