{'fraction_non_alphanumeric': 0.06342981233591546, 'fraction_numerical': 0.018733996694000582, 'mean_word_length': 3.514779045946737, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Heat Kernel and Essential Spectrum of Infinite Graphs

We study the existence and uniqueness of the heat kernel on infinite, locally finite, connected graphs. For general graphs, a uniqueness criterion, shown to be optimal, is given in terms of the maximal valence on spheres about a fixed vertex. A sufficient condition for non-uniqueness is also presented. Furthermore, we give a lower bound on the bottom of the spectrum of the discrete Laplacian and use this bound to give a condition ensuring that the essential spectrum of the Laplacian is empty.


Introduction
The first part of this paper investigates the stochastic completeness of the heat kernel on infinite, locally finite, connected graphs. The heat kernel considered here is a real-valued function of a pair of vertices and a continuous time parameter and is the smallest non-negative fundamental solution for the discrete heat equation. The second section of this paper outlines a construction of the heat kernel using an exhaustion argument. Since this construction is well-known in the case of Riemannian manifolds [2] and was written up in full detail in [17,18] we omit some details. The heat kernel will generate a bounded solution of the heat equation given a bounded initial condition. Stochastic completeness of the heat kernel is equivalent to the uniqueness of this solution.
In the third section of this paper we state a definition of stochastic incompleteness and give several equivalent conditions as presented in [12]. We use one of these conditions, specifically, the existence of a bounded, positive, λ-harmonic function for a negative constant λ, to establish a criterion ensuring the stochastic completeness of the heat kernel on a general graph in terms of the maximum valence on spheres about a fixed vertex. This result should be compared with a result of Dodziuk and Mathai [4,7] which gives uniqueness of bounded solutions of the heat equation for graphs of bounded valence and a result in [17] which gives uniqueness under an assumption on the curvature of the graph.
We then give a similar condition implying the stochastic incompleteness the heat kernel on a general graph. Specifically, we show that if the minimum number of edges leading away from a fixed vertex on the graph increases uniformly at a sufficient rate on spheres of increasing radii then the graph will be stochastically incomplete. In fact, we show that it is sufficient that this condition holds in a subgraph of the entire graph, provided that the subgraph is connected to its complement at a single vertex. We then show that our characterizations of stochastic completeness in terms of the minimum and maximum valence of vertices on spheres about a fixed vertex are optimal by introducing a family of trees we call model. By definition, these trees contain a vertex, here referred to as the root for the model, such that the valence at every other vertex depends only on the distance from the root. These trees are also sometimes called symmetric about the root or radially symmetric with the branching number being the common valence on spheres [10] but we call them model because they are the analogues of rotationally symmetric or model Riemannian manifolds [11,12]. In the case of model trees the sufficient conditions mentioned above are also necessary. In particular, these trees offer examples of infinite, stochastically incomplete graphs, that is, ones for which bounded solutions of the heat equation are not uniquely determined by initial conditions. We also prove two inequalities comparing the heat kernel on a model tree and the heat kernel on a general graph. These inequalities were inspired by an analogous result of Cheeger and Yau on Riemannian manifolds [1].
In the final part of this paper we study the spectrum of the Laplacian on a general graph. We use a characterization of λ 0 (∆), the bottom of the spectrum of the Laplacian, in terms of Cheeger's constant established in [3,6] to give a lower bound for λ 0 (∆) under a curvature assumption on the graph. Using this lower bound and the fact that, when Dirichlet boundary conditions are imposed, the essential spectrum of the Laplacian on the entire graph is the same as the essential spectrum of the graph with a finite subgraph removed [8,10], we then show that the essential spectrum is empty provided that the graph is branching rapidly and the curvature condition is satisfied. This result should be compared with [14] where, for a graph whose Cheeger constant at infinity is positive, rapid branching is shown to be necessary and sufficient for the essential spectrum to be empty.
1.1. Acknowledgments. This paper is based on the author's Ph.D. thesis [18] written under the guidance of Józef Dodziuk. It is a pleasure to thank Professor Dodziuk for his constant support and assistance while this work was carried out. I would also like to thank the referee for many useful comments which greatly improved the exposition of the paper and Matthias Keller for stimulating discussions which led to improvement of results.

The Heat Kernel
2.1. Preliminaries. We now establish our notation and several basic lemmas which will be used throughout. G = (V (G), E(G)) will denote an infinite, locally finite, connected graph without loops or multiple edges where V = V (G) is the set of vertices of G and E = E(G) is the set of edges. We will write x ∈ G when x is a vertex of G. We use the notation x ∼ y to indicate that an edge connects vertices x and y while [x, y] will denote an oriented edge with initial vertex x and terminal vertex y. At times, to be able to write down certain formulas unambiguously, we assume that our graphs are oriented, that is, that every edge has a chosen, fixed orientation, but none of our results depend on the choice of this orientation.
We use the notation m(x) to indicate the valence at a vertex x, that is, m(x) denotes the number of vertices connected by an edge to x. For any two vertices x and y, d(x, y), the distance between x and y, is the number of edges in the shortest path connecting x and y. We let r(x) = d(x, x 0 ) denote the distance between x and a fixed vertex x 0 . By a function on the graph we mean a mapping f : V → R. We will denote the set of all such functions by C(V ). C 0 (V ) will denote the set of all functions on G with finite support. C 0 (V ) is dense in ℓ 2 (V ), the space of all square summable functions on G, Similarly, we let ℓ 2 (Ẽ) denote the Hilbert space of all square summable functions onẼ, the set of all oriented edges of G, with a similarly defined inner product.
If f is a function on the vertices of G then d, the coboundary operator, maps f to a function on oriented edges: where the summation runs over all neighbors of x. It follows immediately from (2.1) that the Laplacian is a bounded operator on ℓ 2 (V ) if and only if the valence of G is bounded, that is, m(x) ≤ M for all vertices x. If D is a finite subgraph of G then int D will denote the interior of D which consists of vertices of D all of whose neighbors are in D, that is, int D = {x | x ∈ D and if y ∼ x then y ∈ D}. The complementary set of vertices in D is called the boundary of D, denoted by ∂D, so that, ∂D = {x | x ∈ D and there exists y ∼ x such that y ∈ D}. An easy calculation gives the following analogue of Green's Theorem: If g vanishes on the boundary of D then we may write this as ∆f, g V (D) = df, dg Ẽ (D) . Furthermore, if f or g is finitely supported then ∆f, g = df, dg . Proof. We give a proof when u satisfies ∆u + ∂u ∂t ≤ 0 and note that the second statement of the lemma follows by considering −u. Let w = u − ǫt for ǫ > 0 so that ∆w + ∂w ∂t ≤ −ǫ < 0. If w has a maximum at ( Since ǫ was arbitrary this implies that Lemma 2.3. Suppose that D is a finite, connected subgraph of G and that u satisfies Proof. At either a maximum or minimum ∂u ∂t (x, t 0 ) = 0 implying that ∆u(x, t 0 ) = x∼x u(x, t 0 ) − u(x, t 0 ) = 0. In either case, this implies that u(x, t 0 ) = u(x, t 0 ) for all x ∼x. Iterating the argument and using the assumption that D is connected gives the statement of the lemma.

2.2.
Construction of the Heat Kernel. As mentioned in the introduction, the construction given here follows the one on open manifolds presented in [2, Section 3] as we exhaust the graph by finite, connected subgraphs, recall a definition of the heat kernel with Dirichlet boundary conditions for each subgraph in the exhaustion, and then pass to the limit. To make our objective precise, for t ≥ 0 and vertices x and y, p t (x, y), the heat kernel, will be the smallest non-negative function smooth in t, satisfying the heat equation ∆p t (x, y) + ∂ ∂t p t (x, y) = 0 in either x or y, and satisfying p 0 (x, y) = δ x (y) where δ x is the delta function at the vertex x. The heat kernel will generate a bounded solution of the heat equation on G for any bounded initial condition. Precisely, for a function u 0 bounded on the vertices of G, u(x, t) = y∈V p t (x, y)u 0 (y) is bounded, smooth for t ≥ 0, and satisfies To begin the construction fix a vertex x 0 ∈ V and let B r = B r (x 0 ) denote the connected subgraph of G consisting of those vertices in G that are at most distance r from x 0 and all edges of G that such vertices span. It follows that B r ⊆ B r+1 and G = ∪ ∞ r=0 B r . We let C(B r , ∂B r ) = {f ∈ C(B r ) | f |∂Br = 0} denote the set of functions on B r which vanish on ∂B r and let ∆ r denote the reduced Laplacian which acts on this space by By Lemma 2.2 solutions of the heat equation on B r with Dirichlet boundary conditions are uniquely determined by initial data. Furthermore, by applying Lemmas 2.1 and 2.3, it follows that ∆ r has a finite set of real eigenvalues 0 < λ r i=0 which form an orthonormal basis for C(B r , ∂B r ). Since ∆ r acts on the finite dimensional vector space C(B r , ∂B r ) we can consider the operator e −t∆r = I − t∆ r + t 2 2 ∆ 2 r − t 3 6 ∆ 3 r + . . . and let p r t (x, y) denote its kernel. Definition 2.4. For vertices x and y in B r and t ≥ 0 p r t (x, y) = e −t∆r δ x , δ y = e −t∆r δ x (y). Proposition 2.5. p r t (x, y) satisfies the following properties: Proof. 1), 2), 3), and 4) are clear from definitions and from the fact that ∆ r is symmetric.
i=0 forms an orthonormal basis for C(B r , ∂B r ), q r t (x, y) satisfies q r 0 (x, y) = δ x (y). Hence, p r t (x, y) and q r t (x, y) are two functions satisfying the heat equation on the interior of B r , both vanish on the boundary ∂B r and satisfy the same initial condition. Therefore, by Lemma 2.2, p r t (x, y) = q r t (x, y). For 6), Lemma 2.2 implies that 0 ≤ p r t (x, y) ≤ 1 for all vertices x and y and t ≥ 0. If there existx andŷ in the interior of B r and t 0 > 0 such that p r t0 (x,ŷ) = 0 then, by Lemma 2.3, since p r t (x, y) satisfies the heat equation in both x and y, it would follow that p r t0 (x, y) = p r t0 (x,ŷ) = 0 for all x and y. In particular, p r t0 (x, x) = 0 implying, from 5), that φ r i (x) = 0 for all i and all x in the interior of B r contradicting the fact that i=0 is, by definition, an orthonormal basis for C(B r , ∂B r ).
To prove 7), we first note that, by 4), y∈Br p r 0 (x, y) = 1 for x ∈ int B r . Then, applying Lemma 2.1 and letting ∆ y denote the Laplacian applied in y, it follows that ∂ ∂t y∈int Br proving the claim.
Extend each p r t (x, y) to be defined for all vertices x and y in G by letting it be 0 for vertices outside of B r . Since B r ⊆ B r+1 it follows by applying Lemma 2.2 that t (x, y) and, combining statements 6) and 7) from Proposition 2.5, that 0 ≤ p r t (x, y) ≤ 1. Therefore, the sequence of heat kernels p r t (x, y) converges as r → ∞ and the heat kernel p t (x, y) can be defined as the limit.
for vertices x and y in V and t ≥ 0.
Dini's Theorem implies that the convergence is uniform in t on every compact subset of [0, ∞). To show that p t (x, y) is differentiable and satisfies the heat where the convergence is uniform on compact subsets of [0, ∞). Therefore, p t (x, y) is differentiable and satisfies the heat equation in both x and y. In fact, iterating this argument shows that p t (x, y) is smooth in t on compact subsets of [0, ∞). From this argument and the corresponding properties of the heat kernels p r t (x, y) statements 1) through 6) of the following theorem now follow.
p is independent of the exhaustion used to define it. 8) p is the smallest non-negative function that satisfies Properties 3) and 6).
y) ≤ 1 and let t → 0. 7) and 8) follow by applying Lemma 2.2. Remark 2.8. If u 0 denotes a bounded function on G then, by combining the properties above, u(x, t) = P t u 0 (x) = y∈V p t (x, y)u 0 (y) is a bounded function, differentiable in t, continuous for t ≥ 0, satisfying (2.2). Remark 2.9. Letting P t u 0 (x) = y∈V p t (x, y)u 0 (y) for u 0 ∈ C 0 (V ), it is also true, as in [2,Proposition 4.5], that P t u 0 (x) = e −t∆ u 0 (x) where∆ is the unique selfadjoint extension of ∆ with domain C 0 (V ) in ℓ 2 (V ). The proof of this fact, and of the essential self-adjointness of the Laplacian, can be found in [17,18].

Stochastic Incompleteness
3.1. Stochastic Incompleteness. Let 1 denote the function which is 1 at every vertex of G. From Property 5) of Theorem 2.7 we know that, for every vertex x and every t ≥ 0, P t 1(x) = y∈V p t (x, y) ≤ 1.
In the next theorem we single out several conditions which are equivalent to stochastic incompleteness. In particular, stochastic incompleteness is equivalent to the non-uniqueness of bounded solutions of the heat equation.
Proof. That 1 ′ ) implies 1) is obvious. To show that 1) implies 1 ′ ) note that if there exists a t 0 such that P t0 1 = 1 then by the semi-group property, part 4) in Theorem 2.7, it follows that P t 1 = 1 for all t. Similarly, if for some x, P t 1(x) = 1 then the proof of Lemma 2.3 will imply that P t 1(x) = 1 for all vertices x.
To show that 2 ′ ) implies 2) we fix a vertex x 0 and let B r = B r (x 0 ) as in the construction of the heat kernel so that B r ⊆ B r+1 and G = ∪ ∞ r=0 B r . We first show that, for every λ < 0, there exists a unique function v r satisfying This follows since the associated homogeneous system obtained by replacing v r |∂Br = 1 with v r |∂Br = 0 in (3.1) has only trivial solutions. To see this, let w be a solution of the homogeneous system and suppose that w is non-zero. We may then assume that there existsx ∈ int B r such that w(x) > 0 andx is a maximum for w on the interior of B r . This implies that ∆w(x) ≥ 0 while ∆w(x) = λw(x) < 0. The contradiction establishes the existence and uniqueness of a solution to (3.1). Let, therefore, v r denote the unique solution of (3.1). We claim that 0 < v r < 1 on the interior of B r and that, if we extend each v r to be 1 outside of B r , then v r ≥ v r+1 . To show that v r > 0 assume that there exists anx in the interior of B r such that v r (x) ≤ 0. We may assume thatx is a minimum for v r from which it follows that ∆v r (x) ≤ 0. On the other hand, ∆v r (x) = λv r (x) ≥ 0 which implies that v r (x) = v r (x) for all x connected tox. Iterating this argument gives a contradiction since v r |∂Br = 1. The other claims are proved in a similar manner. Therefore, {v r } ∞ r=0 is a non-increasing sequence of bounded functions and we let lim r→∞ v r = v with 0 ≤ v ≤ 1 and ∆v = λv. It remains to show that v is non-zero. By arguments given below this will imply that there then exists a positive, bounded function satisfying ∆v = λv. Now, by assumption, there exists a bounded function w such that ∆w ≤ λw and w is non-negative and non-zero. Assuming that |w| < 1, it can be shown that v r ≥ w by a maximum principle argument as used above. It follows that v is non-zero by letting r → ∞.
To show that 2) implies 3) suppose that v is a non-zero, bounded function satisfying ∆v = λv for λ < 0. It follows that, e −λt v and P t v are both bounded solutions of Therefore, by considering the difference of e −λt v and P t v, there exists a non-zero, bounded solution of the heat equation with initial condition equal to 0 for a bounded time interval. By the argument given below this is enough to imply condition 1) which is equivalent to 1 ′ ) and given 1 ′ ), that is, P t 1 < 1, it follows that 1 − P t 1 will give a non-zero, bounded solution of the heat equation with zero initial condition for all time thereby completing the proof. To show that 3) implies 1) suppose that u(x, t) satisfies the conditions in 3). We may assume, by rescaling if necessary, that |u| < 1 and that there exists a vertexx and t 0 > 0 such that u(x, t 0 ) > 0. It follows that w(x, t) = 1 − u(x, t) is bounded, positive, and satisfies with w(x, t 0 ) < 1. Since P t 1 is, by construction, the smallest positive solution to (3.2) it follows that P t0 1(x) ≤ w(x, t 0 ) < 1. We now show that 2) implies 2 ′ ). If v is positive, bounded, and satisfies ∆v = λv then the implication is clear. If the function is only non-zero then, tracing through the proof of the implications 2) ⇒ 3) ⇒ 1) ⇒ 1 ′ ) ⇒ 2) given above, yields the existence of a positive, bounded function satisfying the equation ∆v = λv making the implication, once more, immediate.
Therefore, we have shown the implications 1) ⇔ 1 ′ ) ⇒ 2) ⇔ 2 ′ ) and 2) ⇒ 3) ⇒ 1) which concludes the proof. Therefore, stochastic incompleteness is equivalent to the existence, for every negative λ, of a bounded, positive, λ-harmonic (or λ-subharmonic) function and this criterion will be used to prove several results below.

General Graphs.
For any vertex x 0 of G we let S r (x 0 ), the sphere of radius r about x 0 , denote the set of vertices that are exactly distance r from x 0 and let M x0 (r) denote the maximum valence of the vertices in S r (x 0 ). We now give a criterion for the stochastic completeness of a general graph.

Proof.
Let v be a positive, λ-harmonic function on G for λ < 0. By Theorem 3.2 it suffices to show that v is not bounded. At x 0 , ∆v(x 0 ) = λv(x 0 ) yields By repeating the argument there exists a vertex Iterating the argument and noting that In order to state an analogous criterion for the stochastic incompleteness of a graph we first introduce some more notation. As before, we let x 0 be a fixed vertex of G and, for x ∈ S r (x 0 ), let m ±1 (x) = |{y ∼ x | y ∈ S r±1 (x 0 )}| denote the number of neighbors of x in S r±1 (x 0 ), the next or previous sphere. Let m +1 (r) denote the minimum of m +1 (x) for x ∈ S r (x 0 ) and m −1 (r) the maximum of m −1 (x) for x ∈ S r (x 0 ). Proof. To prove the theorem we define a positive, bounded λ-subharmonic function depending only on the distance from x 0 . Let v(0) = v(x 0 ) > 0 be any positive constant. For x ∈ S 1 (x 0 ) define and, assuming v(r) > v(r − 1), it follows from (3.5) that v(r + 1) > v(r). Therefore, by induction, v(r + 1) > v(r) for all r ≥ 0 and v is positive provided that v(0) > 0. Furthermore, using (3.4) repeatedly it follows that v(r which is finite from the assumption on G. Therefore, v is bounded. It remains to show that v is λ-subharmonic. For r = 0, For x ∈ S r (x 0 ) where r > 0, from (3.5) and the fact that v(r) − v(r − 1) > 0, it follows that thereby completing the proof.
Theorem 3.6 states that a graph will be stochastically incomplete if starting at a fixed vertex x 0 the number of edges leading away from x 0 is growing sufficiently rapidly in all directions from x 0 . The next result states that if we attach an arbitrary graph at x 0 to such a stochastically incomplete graph then the resulting graph will also be stochastically incomplete. To make a precise statement we introduce some notation. If H is a subgraph of G we let H C denote the complementary subgraph of H in G. so that the maximum and minimum are now taken over vertices in H.
and x 0 is the only vertex of H that has a neighbor in H C then G is stochastically incomplete.
Proof. The proof will use the following general statement which states that there always exists a positive, bounded function which is λ-harmonic except at one vertex.
Assuming, for now, Lemma 3.8 we prove Theorem 3.7 by first defining a positive, bounded function v which is λ-harmonic for all vertices x ∈ H C with v(x 0 ) = w(0) = 1. We then make v λ-harmonic at x 0 by letting, for all vertices to define v, a positive, bounded, λ-subharmonic function depending on the distance from x 0 , on the rest of H as in the proof of Theorem 3.6.
We now prove Lemma 3.8: Proof. Let B r = B r (x 0 ) and observe that, for λ < 0, there exists a unique solution of the following system of equations: To see this consider the associated homogeneous system obtained by replacing the second equation in (3.6) by v r (x 0 ) = 0. We will show that the homogeneous system has only trivial solutions. Let w be a solution of the homogeneous system and suppose that w is non-zero. Then we can assume that w(x) > 0 for somex ∈ int B r \ {x 0 } and that w(x) is a maximum for w. It follows that ∆w(x) ≥ 0 while ∆w(x) = λw(x) < 0. The contradiction establishes the existence and uniqueness of a solution to (3.6). One shows that v r , the solution to (3.6), satisfies 0 < v r (x) < 1 for x ∈ int B r \ {x 0 } by maximum principle arguments similar to the one used above. Then, by extending each v r by 0 outside of B r , it follows that v r ≤ v r+1 so that v r → v where v satisfies v(x 0 ) = 1, with 0 < v(x) < 1 and ∆v(x) = λv(x) for all x = x 0 . Remark 3.9. Lemma 3.8 can be generalized to obtain a function v which is not λ-harmonic at finitely many vertices. It can also be applied finitely many times to obtain a more general result then the one presented in Theorem 3.7. Specifically, one can attach to H finitely many disjoint graphs at arbitrary vertices of H and the resulting graph will be stochastically incomplete. However, the stronger result that if G contains a stochastically incomplete subgraph then G is stochastically incomplete is not, in general, true. For example, one can start with T n , a stochastically incomplete model tree (see next subsection for the definition) and, by attaching infinitely many stochastically complete trees (models whose branching number is equal to 1, for example) at each vertex of T n , construct a tree which contains T n and is stochastically complete. See [18] for details. In general, in an unpublished paper, M. Keller showed that any stochastically incomplete graph is a subgraph of a stochastically complete graph constructed in this manner but the number of attached graphs must be infinite.

Model Trees.
We will now show that the characterizations of stochastic completeness and incompleteness in terms of the growth of the valence on spheres given in Theorems 3.4 and 3.6 are optimal by considering a specific family of trees. Suppose that a tree contains a vertex x 0 , referred to from now on as the root for the tree, such that the valence at any other vertex only depends on the distance from x 0 . Therefore, for all x ∈ S r (x 0 ), m(x) = m(r). We will let n(0) = m(x 0 ) and, for r > 0, n(r) = m(r) − 1 denote the branching number of such a tree by which we mean the number of edges on a sphere of radius r about x 0 leading away from x 0 . We call such trees model and denote them throughout by T n . As a consequence of previous results it follows that: Proof. Since, for a model tree T n , n(r) = m +1 (r) = M (r) − 1 and m −1 (r) = 1 for all r > 0, Corollary 3.10 follows by applying Theorems 3.4 and 3.6.
3.4. Heat Kernel Comparison. In this subsection we will prove two inequalities comparing the heat kernel on a model tree and the heat kernel on a general graph. For the Riemannian case see [1, Theorem 3.1]. Throughout, we will denote the heat kernel on the model tree by ρ t (x, y) to distinguish it from p t (x, y), the heat kernel on a general graph. In order to prove our results we will need the following two lemmas concerning the heat kernel on model trees.
Lemma 3.11. Let T n be a model tree with root vertex x 0 and heat kernel ρ t (x, y). Then, for all vertices x ∈ S r (x 0 ), Proof. This is clear from the fact that the Dirichlet heat kernels on The claim is that ϕ(t) > 0 for t > 0. Suppose not, that is, suppose that there exists t 0 > 0 such that ϕ(t 0 ) ≤ 0. Therefore, there exist i 0 < j 0 such that ρ R t0 (i 0 ) ≤ ρ R t0 (j 0 ). We can then assume that ρ R t0 (r) has a global minimum at r = i 0 and a global maximum at r = j 0 for 0 < i < j < R. Then, from ρ R t (0) > ρ R t (1) and ∂ ∂t ρ R t0 (j 0 ) < 0 which implies that ϕ ′ (t 0 ) > 0. It follows that there exists an ǫ > 0 such that for all t ∈ (t 0 − ǫ, t 0 ], ϕ(t) < ϕ(t 0 ) ≤ 0.
Let I denote the maximal interval contained in [0, t 0 ] which contains t 0 and all t < t 0 for which ϕ(t) ≤ 0. It is clear from the continuity of ϕ that I is closed. If I = [a, t 0 ] for some a > 0 then the argument above implies that there exists an ǫ > 0 such that all t ∈ (a − ǫ, a] are in I contradicting the maximality of I. If I = [0, t 0 ] then it would follow that ϕ(0) < 0 contradicting the fact that ϕ(0) = 0. In either case, we obtain a contradiction implying that ϕ(t) > 0 for all t > 0 and, therefore, that ρ R t (r) > ρ R t (r + 1). Letting R → ∞ completes the proof of the lemma.
We are now ready to state and prove the following theorem Theorem 3.13. Let T n denote a model tree with root vertex x 0 and heat kernel ρ t (r) = ρ t (x 0 , x) for x ∈ S r (x 0 ). Let G denote a graph with heat kernel p t (x, y).
Proof. For both 1) and 2) we think of the heat kernel ρ t (x) = ρ t (x 0 , x) on T n as being defined for x ∈ G by letting ρ t (x) = ρ t (r) if x ∈ S r (x ′ 0 ) ⊂ G. We let ∆ G and ∆ Tn denote the Laplacians on G and T n , respectively. For 1) it follows from Lemma 3.12 and from the assumption m +1 (x) ≤ n(r) that, for The second statement is proved using the same techniques.
Remark 3.14. The first result in Theorem 3.13 is an exact analogue of Theorem 3.1 in [1]. For the second result, the additional assumption that m −1 (x) = 1 for all vertices x implies that G is obtained by starting with a tree and then allowing any two vertices on a sphere S r (x ′ 0 ) to be connected by an edge. In particular, for every vertex in such a graph there exists a unique shortest path connecting that vertex to x ′ 0 . df, df f, f .

Essential Spectrum
Therefore, λ 0 (∆ r ) ≥ λ 0 (∆ r+1 ) and the bottom of the spectrum of the Laplacian is defined as the limit λ 0 (∆) = lim r→∞ λ 0 (∆ r ). One could also let λ 0 ∆f,f f,f . We now state the following theorem which, in the Riemannian setting, is given in [16, Theorem 2.1] (see also [9,Lemma 1]) and, in the case of the combinatorial Laplacian, in [5, Proposition 1.5]. Proof. For λ ≤ λ 0 (∆) ≤ λ 0 (∆ r ) note that, as in the proof of the implication 2) ⇒ 2 ′ ) of Theorem 3.2, there exists a function satisfying ∆v r = λv r on the interior of B r such that v r|∂Br = 1. It was shown there that 0 < v r < 1 on the interior of B r . Let w r = vr vr (x0) to obtain a positive function which is λ-harmonic on the interior of B r and satisfies w r (x 0 ) = 1. By a Harnack inequality argument the sequence {w r (x)} ∞ r=0 is bounded for every fixed vertex therefore, by the diagonal process, we may find a subsequence which converges for all vertices (see [5,Proposition 1.5] and [18] for details). This gives the proof of the first statement.
For the second statement, if v is a positive function satisfying ∆v = λv then u(x, t) = e −λt v(x) and w(x, t) = y∈Br p r t (x, y)v(y) both satisfy the heat equation on int B r ×[0, T ]. Applying Lemma 2.2 to u−w implies that u−w ≥ 0 on B r ×[0, T ]. Therefore, e −λt v(x) ≥ y∈Br p r t (x, y)v(y), which we write as By applying Lemma 2.3, φ r 0 can be chosen so that φ r 0 (x) > 0 for x in the interior of B r . Therefore, if λ > λ r 0 = λ 0 (∆ r ) then the right hand side of (4.1) would go to ∞ as t → ∞. Hence, λ ≤ λ 0 (∆ r ) for all r implying λ ≤ λ 0 (∆).

Lower Bounds.
We now use the approach in [5] to prove a lower bound on the bottom of the spectrum under a curvature assumption on the graph. In order to take advantage of a lower bound on the bottom of the spectrum in terms of Cheeger's constant proved in [6] we have to introduce an operator related to the Laplacian ∆. Specifically, we denote by ∆ bd the bounded or combinatorial Laplacian which is given by This operator acts on the Hilbert space with inner product f, g bd = x∈V m(x)f (x)g(x). ∆ bd is a self-adjoint, bounded operator with ||∆ bd || ≤ 2. Furthermore, using the technique in the proof of Theorem 3.4, it can be shown that the heat kernel associated to ∆ bd , that is, e −t∆ bd δ x (y), is stochastically complete for all graphs. In particular, since the various characterizations of stochastic incompleteness given in Theorem 3.2 hold for ∆ bd as well as for ∆, bounded solutions of the heat equation involving ∆ bd are uniquely determined by initial conditions for any graph [18]. The bottom of the spectrum of ∆ bd is, as for ∆, given by For any finite subgraph D of G we let L(∂D) = |{y ∼ x | x ∈ D, y ∈ D}| denote the number of edges with exactly one vertex in D and A(D) = x∈D m(x). Cheeger's constant is then be defined as α(G) = inf D⊂G D finite
In fact, the proof in [6] applies in the following more general context. Let A denote a finite subgraph of G and let ∆ bd,G\A denote the reduced bounded Laplacian which is equal to ∆ bd on the complement of A and 0 on A. ∆ bd,G\A acts on the space of ℓ 2 bd functions which vanish on A. If α(G \ A) = inf D finite
As usual, we fix a vertex x 0 ∈ G and let r(x) = d(x, x 0 ). We let m +1 (x) = |{y ∼ x | r(y) = r(x)+1}| and m −1 (x) = |{y ∼ x | r(y) = r(x)−1}| denote the number of vertices that are 1 step further and 1 step closer to x 0 then is x as before. It follows by an easy calculation that m+1(   Proof. The first statement is a direct consequence of Lemma 4.2 and (4.2). To obtain the second statement note that, for any finitely supported function f , ∆ bd f, f bd = ∆f, f while, if m(x) ≥ m, then f, f bd ≥ m f, f . This estimate and the first statement in the theorem then combine to give We first recall a characterization of the essential spectrum. It can be shown that λ is in the essential spectrum of ∆, denoted λ ∈ σ ess (∆), if and only if there exists a sequence f i in the domain of ∆ which is orthonormal and satisfies ∆f i − λf i → 0 [15, Theorem VII.12 and remarks following Theorem VIII.6]. Here, the domain of ∆ consists of f ∈ ℓ 2 (V ) such that ∆f ∈ ℓ 2 (V ). We denote by ∆ G\Br the reduced Laplacian which is equal to ∆ on the complement of B r and 0 on B r as in the previous subsection. Using the characterization of the essential spectrum mentioned above one shows that  Proof. Applying (4.4) in Theorem 4.3 to λ 0 (∆ G\Br ) implies that λ 0 (∆ G\Br ) → ∞ as r → ∞ since m c (r) → ∞. Meanwhile, by Lemma 4.4, the essential spectrum of ∆ remains unchanged after the removal of B r . Since the essential spectrum is a subset of the spectrum the result follows.