9512.net

# Geometric and spectral properties of locally tessellating planar graphs

Geometric and spectral properties of locally tessellating planar graphs

arXiv:0805.1683v1 [math.SP] 12 May 2008

Matthias Keller ? TU Chemnitz Fakult¨ at f¨ ur Mathematik D-09107 Chemnitz, Germany

Norbert Peyerimho? ? Department of Math. Sciences University of Durham Durham DH1 2LE, UK

May 12, 2008

Abstract In this article, we derive bounds for values of the global geometry of locally tessellating planar graphs, namely, the Cheeger constant and exponential growth, in terms of combinatorial curvatures. We also discuss spectral implications for the Laplacians.

1

Introduction

A locally tessellating planar graph G is a tiling of the plane with all faces to be polygons with ?nitely or in?nitely many boundary edges (see Subsection 2.1 for precise de?nitions). The edges of G are continuous recti?able curves without self-intersections. Faces with in?nitely many boundary edges are called in?nigons and occur, e.g., in the case of planar trees. The sets of vertices, edges and faces of G are denoted by V , E and F . d(v, w) denotes the combinatorial distance between two vertices v, w ∈ V , where each edge is assumed to have combinatorial length one. Useful local concepts of the graph G are combinatorial curvature notions. The ?nest curvature notion is de?ned on the corners of G . A corner is a pair (v, f ) ∈ V ×F , where v is a vertex of the face f . The set of all corners is denoted by C . The corner curvature κC is then de?ned as κC (v, f ) = 1 1 1 + ? , |v | |f | 2

where |v | and |f | denote the degree of the vertex v and the face f . If f is an in?nigon, we set |f | = ∞ and 1/|f | = 0. The curvature at a vertex v ∈ V is given by the sum κ(v ) =
(v,f )∈C
? e-mail: ? e-mail:

κC (v, f ) = 1 ?

|v | + 2

f :v ∈f

1 . |f |

matthias.keller@mathematik.tu-chemnitz.de norbert.peyerimho?@durham.ac.uk

1

For a ?nite set W ? V we de?ne κ(W ) = v∈W κ(v ). These combinatorial curvature de?nitions arise naturally from considerations of the Euler characteristic and tessellations of closed surfaces, and they allow to prove a combinatorial Gau?-Bonnet formula (see [BP1, Thm 1.4]). Similar combinatorial curvature notions have been introduced by many other authors, e.g., [Gro, Hi, St, Woe]. The aim of this paper is to establish connections between local curvature conditions and characteristic values of the global geometry of the graph G , in particular the exponential growth and Cheeger constants. For a ?nite subset W ? V , let vol(W ) = v∈W |v |. The exponential growth is de?ned as follows (note that the value ?(G ) does not depend on the choice of center v ∈ V ): De?nition 1. The exponential growth ?(G ) is given by ?(G ) = lim sup
n→∞

log vol(Bn (v )) , n

where Bn (v ) = {w ∈ V | d(v, w) ≤ n} denotes the (combinatorial) ball of radius n about v . We also consider the following two types of Cheeger constants. De?nition 2. Let α(G ) =
W ? V, |W | < ∞

inf

|?E W | |W |

and

α(G ) =

W ? V, |W | < ∞

inf

|?E W | vol(W )

where ?E W is the set of all edges e ∈ E connecting a vertex in W with a vertex in V\W . α(G ) is called the physical Cheeger constant and α(G ) the combinatorial Cheeger constant of the graph G . The attributes physical and combinatorial in the previous de?nition are motivated by the fact that these Cheeger constants are closely linked to two types of Laplacians: The physical Laplacian is used frequently in the community of Mathematical Physicists and is de?ned as follows: (??)(v ) = |v |?(v ) ? ?(w).
w ?v

(1)

Note that ? is an unbounded operator if there is no bound on the vertex degree of G . The combinatorial Laplacian ? is a bounded operator and appears in the context of spectral geometry (see, e.g., [DKa, DKe, Woe2]): (??)(v ) = ?(v ) ? 1 ?(u). |v | u?v (2)

Both operators are de?ned in and are self-adjoint with respect to di?erent l2 spaces (see Subsection 2.2). In the case of ?xed vertex degree, both operators are multiples of each other. Our main geometric results are given in Subsection 2.3, where we ? provide lower bounds for both Cheeger constants in terms of combinatorial curvatures (see Theorem 1 below), 2

? provide upper bounds for the exponential growth in terms of an upper vertex bound (see Theorem 2 below). Even though Theorem 2(b) is formulated in terms of bounds on vertex and face degrees, it can also be considered as an estimate in terms of combinatorial curvature, as is explained in the remark following the theorem. In fact, the proof is based on the corresponding curvature version. Now we discuss connections to the spectrum. The Cheeger constant and the exponential growth were ?rst introduced in the context of Riemannian manifolds and were useful invariants to estimate the bottom of the (essential) spectrum of the Laplacian (see [Che] and [Br]). An analogous inequality between the Cheeger constant and the bottom of the spectrum in the discrete case of graphs was ?rst proved by [Do] and [Al]. This inequality is also useful in the study of expander graphs. [Al] noted also the connection between this inequality and the Max Flow-Min Cut Theorem (see also [Chu] and [Gri]). For other connections between isoperimetric inequalities and lower bounds of eigenvalues in both continuous and discrete settings see, e.g., [CGY]. The best results about the relations between the combinatorial Cheeger constant, the exponential growth, and the bottom λ0 (G ) and λess 0 (G ) of the (essential) spectrum of the combinatorial Laplacians ? are due to K. Fujiwara (see [Fu1] and [Fu2]): 1? 1 ? α2 (G ) ≤ λ0 (G ) ≤ λess 0 (G ) ≤ 1 ? 2e?(G )/2 . 1 + e?(G ) (3)

These estimates are sharp in the case of regular trees. Using these estimates and Theorems 1 and 2, we obtain ? lower and upper estimates on the bottom of the (essential) spectrum of the combinatorial Laplacian in terms of combinatorial curvature (see Corollaries 1 and 2). Since there are estimates to compare the bottom of the (essential) spectrum of the combinatorial Laplacian with the physical Laplacian (see for instance [Ke]) these results can be also formulated for the physical Laplacian. A lower estimate for the bottom of the essential spectrum of the combinatorial Laplacian via the combinatorial Cheeger constant at in?nity can be found in [Fu2, Cor. 3]. This yields a discrete analogue for the combinatorial Laplacian of the result in [DL] about the emptiness of the essential spectrum for complete simply connected manifolds with curvature converging to minus in?nity. Corresponding results about the emptiness of the essential spectrum for the physical Laplacian can be found in [Ke, Woj]. Finally, let us discuss two other interesting types of eigenfunctions, namely, strictly positive eigenfunctions and ?nitely supported eigenfunctions, and illustrate all concepts in two examples. For the discrete case of a graph, it was shown in [DKa, Prop. 1.5] that the equation ?f = λf has a positive solution if and only if λ ≤ λ0 (G ). This characterisation of the bottom of the spectrum was well known before in the context of Riemannian manifolds (see, e.g., [Sull] and the references therein). In the reverse direction, this characterisation might be used in concrete cases to determine the bottom of the spectrum of an in?nite graph. 3

On the other hand, ?nitely supported solutions of the equation ?f = λf are obviously l2 -eigenfunctions and, therefore, they can only exist for eigenvalues λ ≥ λ0 (G ). Existence of ?nitely supported eigenfunctions in Penrose tilings was ?rst observed in [KS]. Their existence is a purely discrete phenomenon, since in the case of a non-compact, connected Riemannian manifold the eigenvalue equation ?f = λf cannot have compactly supported eigenfunctions (a fact which is known as the unique continuation principle; see [Ar]). These ?nitely supported eigenfunctions coincide with the discontinuities of the integrated density of states (or spectral density function). See, e.g., the articles [KLS, LV] and the references therein for more details about this connection. Examples. (a) We consider the periodic tessellation G = (V , E , F ) in Figure 1. We assume that all edges are straight Euclidean segments of length one.

v

Figure 1: Plane tessellation with regular triangles and hexagons We ?rst show that ?(G ) = 0: Choose a ?xed radius 0 < r < 1/2. Then all Euclidean balls of radius r centered at all vertices in V are pairwise disjoint. On the other hand, the vertices in the combinatorial ball Bn (v ) are contained in the Euclidean ball of radius n, centered at v . Both facts together imply that combinatorial balls grow only polynomially and the exponential growth is zero. As a consequence, this graph cannot contain a binary tree as a subgraph. Moreover, using (3), we conclude that λ0 (G ) = λess 0 (G ) = 0 and α(G ) = α(G ) = 0.

Finally, G does admit ?nitely supported eigenfunctions, namely, choose p ∈ R2 to be the center of a hexagon and de?ne f (p + e2πi/6 ) = (?1)i (i.e., choose alternating values 1, ?1, 1, ?1, 1, ?1 clockwise around the vertices of the hexagon) and f (v ) = 0 for all other vertices. Then we have ?f = 3 2f. (b) Let Tp denote the p-regular tree. In this case, spectrum and essential spectrum of the combinatorial Laplacian coincide and are given by the interval (see, e.g., [Sun, App. 3]) √ √ 2 p?1 2 p?1 1? . ,1 + p p 4

Consequently, ?f = λf admits a positive solution if and only if λ ≤ 1 ? √ 2 2 p ? 1/p. Moreover, we have α(Tp ) = p? p , α(Tp ) = p ? 2 and ?(Tp ) = log(p ? 1). Note that a regular tree doesn’t admit l2 -eigenfunctions. For otherwise, we could choose a vertex v at which our eigenfunction doesn’t vanish and take its radialisation with respect to this vertex. This radialisation would be again a non-vanishing l2 -eigenfunction with the same eigenvalue and, since its values would only depend on the distance to v , there would be an easy recursion formula for its values. The precise form of the recursion formula would then contradict to the requirement that the function lies in l2 . Acknowledgements. Matthias Keller would like to thank Daniel Lenz who encouraged him to study the connection between curvature and spectral theory. Matthias Keller was supported during this work by the German Business Foundation (sdw).

2

Basic notions and main results

In the ?rst two subsections, we provide the notions which haven’t yet been introduced in full detail in the Introduction. In Subsections 2.3 and 2.4, we state our main results.

2.1

Locally tessellating planar graphs

Let G = (V , E ) be a planar graph (with V and E the set of vertices and edges) embedded in R2 . The faces f of G are the closures of the connected components in R2 \ e∈E e. The set of faces is denoted by F . We further assume that G has no loops, no multiple edges and no vertices of degree one (terminal vertices). We write e = vw, if the edge e connects the vertices v, w. Moreover, we assume that every vertex has ?nite degree and that every bounded open set in R2 meets only ?nitely many faces of G . We call a planar graph with these properties simple. The boundary of a face f is the subgraph ?f = (V ∩ f, E ∩ f ). We call a sequence of edges e1 , . . . , en a walk of length n if there is a corresponding sequence of vertices v1 , . . . , vn+1 such that ei = vi vi+1 . A walk is called a path if there is no repetition in the corresponding sequence of vertices v1 , . . . , vn . A simple planar graph G is called a locally tessellating planar graph if the following additional conditions are satis?ed: i.) Any edge is contained in precisely two di?erent faces. ii.) Any two faces are either disjoint or have precisely a vertex or a path of edges in common. In the case that the length of the path is greater then one, then both faces are unbounded. iii.) Any face is homeomorphic to the closure of an open disc D ? R2 , to R2 \ D or to the upper half plane R × R+ ? R2 and its boundary is a path. Note that these properties force the graph G to be connected. Examples are tessellations R2 introduced in [BP1, BP2], trees in R2 , and particular ?nite tessellations on the sphere mapped to R2 via stereographic projection.

5

When we consider the vertex degree as a function on V we write deg(v ) = |v | for v ∈ V . Moreover we de?ne the degree |f | of a face f ∈ F to be the length of the shortest closed walk in the subgraph ?f meeting all its vertices. If there is no such ?nite walk we set |f | = ∞. v ? w means that d(v, w) = 1, i.e., v and w are neighbors. A (?nite or in?nite) path with associated vertex sequence . . . vi vi+1 vi+2 . . . is called a geodesic, if we have d(vi , vj ) = |i ? j | for all pairs of vertices in the path.

2.2

Laplacians

Let G = (V , E , F ) be a locally tessellating planar graph. The operators ? and ? were already introduced in (1) and (2). They are symmetric operators and initially de?ned on the space cc (V ) := {? : V→R | |supp ?| < ∞} of functions with ?nite support. However, they have unique self-adjoint extensions on di?erent l2 -spaces: Let g : V → (0, ∞) be a weight function on the vertices of the graph G and l2 (V , g ) := {? : V→R | ?, ?
g

:=
v ∈V

g (v )|?(v )|2 < ∞}.

For g = 1 we simply write l2 (V ). Then the combinatorial Laplacian can be extended to a bounded self-adjoint operator on all of l2 (V , deg). The physical Laplacian has also a unique selfadjoint extension in the space l2 (V ) (see [We] or [Woj]). Note, however, that the adjacency operator need not be essentially self adjoint (see [MW, Section 3] and the references therein). We denote the self-adjoint extensions of both Laplacians, again, by ? and ?. Furthermore, we de?ne the restriction of the combinatorial Laplacian on the complement of a ?nite set K of vertices. Let PK : l2 (V , deg)→l2 (V \ K, deg) be the canonical projection and iK : l2 (V \ K, deg)→l2 (V , deg) be its dual operator, which is the continuation by 0 on K . We write ?K = PK ?iK . Of particular importance is the bottom of the spectrum λ0 (G ) and of the essential spectrum λess 0 (G ). λ0 (G ) can be characterised as the in?mum of the Rayleight-Ritz quotient over all non-zero functions f ∈ l2 (V , deg), i.e., λ0 (G ) = inf ?f, f deg : f = 0, f ∈ l2 (V , deg) . f, f deg

Similarly, λess 0 (G ) can be obtained via λess 0 (G ) = lim inf
n→∞

?Bn f, f deg : f = 0, f ∈ l2 (V\Bn , deg) , f, f deg

(4)

where Bn are balls of radius n around any ?xed vertex v ∈ V . A proof of (4) can be found in [Ke]. Obviously, we have λ0 (G ) ≤ λess 0 (G ). Equality holds in the following case:

6

Proposition 1. Assume that there is a subgroup Γ of the automorphism group of G with supγ ∈Γ d(v, γv ) = ∞ for some vertex v ∈ V . Then we have λ0 (G ) = λess 0 (G ). Proof. For the bottom of the spectrum not to lie in the essential spectrum would mean that it is an isolated eigenvalue of ?nite multiplicity. But this cannot be the case (see Fact 1 in [Sun, p. 259]). Analogous statements hold for the bottom of the (essential) spectrum of the physical Laplacian.

2.3

Cheeger constant and exponential growth estimates

The physical and combinatorial Cheeger constants were introduced in De?nition 2. It is easy to see that they are linked to the physical and combinatorial Laplacians via the equations: α(G ) = inf ?χW , χW χ W , χW and α(G ) = inf ?χW , χW χ W , χW
deg deg

W ? V, |W | < ∞

W ? V, |W | < ∞

,

where χW denotes the characteristic function of the set W ? V . Note, in particular, that the combinatorial Cheeger constant is always bounded from above by α(G ) ≤ 1. Next, we state the Cheeger constant estimates: Theorem 1. Let G = (V , E , F ) be a locally tessellating planar graph and 3 ≤ q ≤ ∞} such that |f | ≤ q for all faces f ∈ F . (a) For some a > 0, let κ(v ) ≤ ?a for all v ∈ V . Then we have α(G ) ≥ (b) For some c > 0, let
1 |v | κ(v )

2q a. q?2

≤ ?c for all v ∈ V . Then we have α(G ) ≥ 2q c. q?2

Moreover, the above estimates are sharp in the case of regular trees. (Note that q in the case q = ∞ we set q2 ?2 = 2.) Remark. The combinatorial Cheeger constant of all non-positively curved regular plane tessellation Gp,q (with all vertices satisfying |v | = p and faces satisfying |f | = q ) was explicitly calculated in [HJL] and [HiShi] as α(Gp,q ) = Our estimate gives in this case α(Gp,q ) ≥ (p ? 2)(q ? 2) ? 4 . p(q ? 2) 7 p?2 p 1? 4 . (p ? 2)(q ? 2)

Before considering the exponential growth of a locally tessellating planar graph G = (V , E , F ), let us ?rst introduce the cut locus Cut(v ) of a vertex v ∈ V . Cut(v ) denotes the set of all vertices w, at which dv := d(v, ·) attains a local maximum, i.e., we have w ∈ Cut(v ) if dv (w′ ) ≤ dv (w) for all w′ ? w. G is without cut locus if Cut(v ) = ? for all v ∈ V . Obviously, the cut locus of a ?nite graph is never empty. It was proved in [BP2, Thm. 1] that plane tessellations with everywhere non-positive corner curvature are graphs without cut locus. Moreover, let Tp denote the regular tree with |v | = p for all vertices. Theorem 2. Let G = (V , E , F ) be a locally tessellating planar graph without cut locus. (a) If there exists p ≥ 3 such that |v | ≤ p then we have ?(G ) ≤ ?(Tp ) = log(p ? 1). (b) If there exist p ≥ 3 such that (5) is satis?ed and q ∈ {3, 4, 6} such that |f | = q ? f ∈ F, ? (i.e., G is face-regular) then we have ? 2 p + ?(G ) ≤ ?(Gp,q ) = log ? ? 2 q?2 ? v ∈ V, (5)

2 p ? 2 q?2

2

? 1? .

Remark. For the reader’s convenience, Theorem 2(b) was stated in “more familiar” terms of vertex and face degrees. However, the statement has an equivalent reformulation in terms of curvature: Let G be a locally tessellating planar graph without cut locus satisfying |f | = q for all faces and q ∈ {3, 4, 6}. For some b ≥ 0, let ?b ≤ κ(v ) for all v ∈ V . Then we have ?(G ) ≤ log(τ + τ 2 ? 1),
q where τ = 1+ q? 2 b ≥ 1. The inequality is sharp (with the optimal choice of b) in the case of regular graphs Gp,q . In fact, the proof will be given for this equivalent reformulation. (Note that the constants p and b in the two formulations are 2 related by b = q? q p ? 1.)

Since the regular plane tessellations Gp,q can be considered as combinatorial analogues of constant curvature space forms in Riemannian geometry, it is natural to conjecture the following discrete version of a Bishop volume comparison result (see, e.g., [GaHuLa, Theorem 3.101] for the case of a Riemannian manifold). Conjecture. Let p, q ≥ 3 with 1/p + 1/q ≤ 1/2 be given. Then we have ?(G ) ≤ ?(Gp,q ), (6) for all locally tessellating planar graphs G = (V , E , F ) without cut locus satisfying |v | ≤ p, |f | ≤ q . 8

Theorem 2 con?rms this conjecture for the cases q = 3 and q = ∞. However, it seems di?cult to prove this seemingly obvious estimate (6) for general face degree bounds q ≥ 3. Assuming the above conjecture to be true, the comparison of the exponential growth of a locally tessellating planar graph with upper vertex degree bound p and of the regular tree Tp , as given in Theorem 2(a), is quite good if all faces of G satisfy |f | ≥ 6. For example, we have in the case (p, q ) = (5, 6): √ 1.307 · · · = log(2 + 3) = ?(G5,6 ) ≤ ?(T5 ) = log 4 = 1.381 . . . . An direct consequence of [BP1, Corollary 5.2] is the following lower bound for the exponential growth: Theorem 3. Let G = (V , E , F ) be a locally tessellating planar graph without cut locus and a > 0 such that κ(v ) ≤ ?a for all vertices v ∈ V . Assume there is 3 ≤ q ≤ ∞ such that we have |f | ≤ q for all faces f ∈ F . Then we have ?(G) ≥ log 1 + 2q a . q?1

Moreover, this estimate is sharp in the case of regular trees. (In the case q = ∞, q we set q2 ?1 = 2.) We like to ?nish this subsection by a few additional useful facts: Let Sn (v ) = {w ∈ V | d(v, w) = n} be the (combinatorial) sphere of radius n about v ∈ V . If there is a uniform upper bound on the vertex degree and if sn := |Sn (v )| is a non-decreasing sequence, one easily checks that ?(G ) = lim sup
n→∞

log sn . n

(7)

Yet another Cheeger constant h(G ) was considered in [BS]: h(G ) =
W ? V, |W | < ∞

inf

|?V W | , |W |

where ?V W is the set of all vertices v ∈ V\W which are end points of an edge in ?E W . In the case that ?(G ) is presented by (7), this Cheeger constant is related to the exponential growth by e?(G ) ≥ 1 + h(G ), with equality in the case of regular trees.

2.4

Spectral applications

An immediate consequence of Fujiwara’s lower estimate (3) and Theorem 1 is the following combinatorial analogue of McKean’s Theorem (see [McK] for the case of a Riemannian manifold):

9

Corollary 1 (Combinatorial version of McKean’s Theorem). Let G = (V , E , F ) be a locally tessellating planar graph and 3 ≤ q ≤ ∞ such that |f | ≤ q for all 1 faces f ∈ F . For some c > 0, let |v | κ(v ) ≤ ?c for all v ∈ V . Then we have 1? 1? 2q c q?2
2

≤ λ0 (G ).

This estimate is sharp in the case of regular trees. Combining Theorem 2(a), the curvature version of Theorem 2(b) (see the remark of the theorem) and Fujiwara’s upper estimate (3), we obtain: Corollary 2. Let G = (V , E , F ) be a locally tessellating planar graph without cut locus. (a) If there exists p ≥ 3 such that |v | ≤ p then we have λess 0 (G ) ≤ λess 0 (Tp ) ? v ∈ V, √ 2 p?1 =1? . p (8)

(b) If there exist q ∈ {3, 4, 6} with |f | = q for all f ∈ F , and b > 0 with ?b ≤ κ(v ) for all v ∈ V , then we have √ 2 τ + τ2 ? 1 √ , λess ( G ) ≤ 1 ? 0 1 + τ + τ2 ? 1 where τ = 1 +
q q ?2 b .

Next we indicate implications of the above results for the spectrum of the physical Laplacian. Let λ0 (G ) and λess ) (G ) denote the bottom of the (essential) spectrum of the physical Laplacian ? and, for n ≥ 0, let mn =
w ∈V \Bn?1 (v )

inf

|w|

and Mn =

sup
w ∈V \Bn?1 (v )

|w|,

where v ∈ V is an arbitrary vertex and B?1 (v ) = ?. Moreover let m∞ = limn→∞ mn and M∞ = limn→∞ Mn . Then we have, by [Do] λ0 (G ) ≥ α(G )2 2M and λess 0 (G ) ≥ α∞ (G )2 , 2M∞ (9)

where α∞ (G ) denotes the physical Cheeger constant at in?nity, de?ned in [Ke]. In general we can also estimate, as demonstrated in [Ke], m0 λ0 (G ) ≤ λ0 (G ) ≤ M0 λ0 (G )
ess ess and m∞ λess 0 (G ) ≤ λ0 (G ) ≤ M∞ λ0 (G ).

Via this inequalities we can estimate the bottom of the (essential) spectrum of the physical Laplacian ? by the estimates of Corollary 1 and 2 for the combinatorial Laplacian. Before we look at an explicit example, let us mention the following result about the absence of ?nitely supported eigenfunctions in the case of non-positive corner curvature: 10

Theorem 4 (see [KLPS, Theorem 4]). Let G = (V , E , F ) be a plane tessellation (in the restricted sense of [BP2]) with non-positive corner curvature in all corners. Then the combinatorial Laplacian does not admit ?nitely supported eigenfunctions. Note that Theorem 4 becomes wrong if we replace “non-positive corner curvature” by the weaker assumption “non-positive vertex curvature”, since Example (a) of the Introduction is a graph with vanishing vertex curvature which admits ?nitely supported eigenfunctions. Let us, ?nally, apply the above results in an example. Example. We consider the regular tessellation G6,6 . Using our geometric results in this article, we obtain √ 1 + 21 1 and ?(G6,6 ) = log ≈ 1.5668. α(G6,6 ) ≥ 2 2 Proposition 1 tells us that λ0 (G6,6 ) = λess 0 (G6,6 ), and with our results in this Subsection we can conclude that √ √ √ 3 3+ 7 ess √ λ0 (G6,6 ) = λ0 (G6,6 ) ∈ 1? ,1 ? 2 2 7 + 21 ≈ [0.1340, 0.2441].

Using the explicit formula for the Cheeger constant in [HJL] in this particular 1 ≈ 0.5774 and we can shrink this interval to case, we obtain α(G6,6 ) = √ 3 λ0 (G6,6 ) = λess 0 (G6,6 ) ∈ ≈ 1? √ √ 2 3+ 7 √ ,1 ? 2 3 7 + 21

[0.1835, 0.2441].

Note that the physical Laplacian is just a multiple of the combinatorial Laplacian (? = 6?). Finally, Theorem 4 guarantees that there are no ?nitely supported eigenfunctions in G6,6 .

3

Proof of Theorem 1

The heart of the proof of Theorem 1 is Proposition 2 below. An earlier version of this proposition in the dual setting (see [BP1, Prop. 2.1]) was originally obtained by helpful discussions with Harm Derksen. Let us ?rst introduce some important notions related to a locally tessellating planar graph G = (V , E , F ). For a ?nite set W ? V let GW = (W, EW , FW ) be the subgraph of G induced by W , where EW are the edges in E with both end points in W and FW are the faces induced by the graph (W, EW ). Euler’s formula states for a ?nite and connected subgraph GW (observe that FW contains also the unbounded face): |W | ? |EW | + |FW | = 2. (10) By ?F W , we denote the set of faces in F which contain an edge of ?E W . Moreover, we de?ne the inner degree of a face f ∈ ?F W by |f |i W = |f ∩ W |. 11

In the following, we need the two important formulas which hold for arbitrary ?nite and connected subgraphs GW = (W, EW , FW ). The ?rst formula is easy to see and reads as |v | = 2|EW | + |?E W |. (11)
v ∈W

Since W is ?nite, the set FW contains at least one face which is not in F , namely the unbounded face surrounding GW , but there can be more. De?ne C (W ) = |FW | ? |FW ∩ F | ≥ 1. Note that |FW ∩ F | is the number of faces in F which are entirely enclosed by edges of EW . Sorting the following sum over vertices according to faces gives the second formula 1 |f | = |FW ∩ F | + |f |W |f | |f |W . |f |
i i

v ∈W f ?v

f ∈?F W

=

|FW | ? C (W ) +

(12)

f ∈?F W

Proposition 2. Let G = (V , E , F ) be a locally tessellating planar graph and W ? V be a ?nite set of vertices such that the induced subgraph GW is connected. Then we have κ(W ) = 2 ? C (W ) ? |?E W | + 2 |f |i W |f |

f ∈?F W

Proof. By the equations (11), (12) and (10) we conclude ? ? 1 ? ?1 ? |v | + κ(W ) = 2 |f |
v ∈W f ?v

= |W | ? |EW | ? = 2 ? C (W ) ?

|?E W | + |FW | ? C (W ) + 2
i |f |W f ∈?F W

f ∈?F W

|f |W |f |

i

|?E W | + 2

|f |

.

Proposition 3. Let G = (V, E, F ) be a locally tessellating planar graph and 3 ≤ q ≤ ∞ such that |f | ≤ q for f ∈ F . Let W ? V be a ?nite set of vertices such that the induced subgraph GW is connected. Then we have |?E W | ≥ 2q (2 ? C (W ) ? κ(W )). q?2

Proof. Since G is locally tessellating, every edge e ∈ ?E W separates precisely two di?erent faces. The edge obtains a direction by its start vertex to be in V\W and its end vertex to be in W . Thus it makes sense to refer to the faces at the left and right side of the edge e. Thus every edge e ∈ ?E W determines a unique corner (v, f ) ∈ W × ?F W , where v ∈ W is the end vertex of e and f is

12

the face at the left side of e. The so de?ned map ?E W → W × ?F W is clearly injective, and thus we have |f |W = |{(v, f ) ∈ W × ?F W : v ∈ f }| ≥ |?E W |.
i

f ∈?F W

Using this fact and |f | ≤ q for all f ∈ F , we conclude with Proposition 2 2 ? C (W ) ? κ(W ) = |?E W | ? 2 |f |W ≤ |?E W | |f |
i

f ∈?F W

1 1 ? 2 q

,

which proves the inequality in the proposition. Note that the Cheeger constants in De?nition 2 are obtained by taking the in?mum of a particular expression over all ?nite subsets W ? V . In fact, we can restrict ourselves to consider only ?nite sets W for which the induces graph GW is connected. This follows from the observation that, for a given ?nite set W ? V , we can always ?nd a non-empty subset W0 ? W such that GW0 is a connected component of Gw and that |?E W0 |/vol(W0 ) ≤ |?e W |/vol(W ) or |?E W0 |/|W0 | ≤ |?e W |/|W |, respectively. We can reduce the sets under consideration even further. Let W ? V be a ?nite set such that GW is connected. Note that Gw has only one unbounded face. By adding all vertices of V contained in the union of all bounded faces of Gw , we obtain a bigger ?nite set PW ? W such that C (PW ) = 1. (Note that all bounded faces of GPW are also faces of the original graph G .) We call a ?nite set P ? V with connected graph GP and C (P ) = 1 a polygon. Clearly, we have |?E PW |/vol(PW ) ≤ |?e W |/vol(W ) and |?E PW |/|PW | ≤ |?e W |/|W |. Thus it su?ces for the de?nition of the Cheeger constants to take the in?mum only over all polygons. With this ?nal observation we can now prove Theorem 1. Proof of Theorem 1. Let W ? V be a polygon. Since C (W ) = 1, we conclude from Proposition 3 that |?E W | 2q ?κ(W ) 2q ≥ ≥ a. |W | q ? 2 |W | q?2 Taking the in?mum over all polygons yields part (a) of the theorem. For the proof of part (b), recall that ?κ(v ) ≥ c · |v | for all vertices v ∈ V . This implies that ? v∈W κ(v ) ?κ(W ) = ≥ c, vol(W ) v ∈W |v | and, consequently, for polygons W ? V , |?E W | 2q ?κ(W ) 2q ≥ ≥ c. vol(W ) q ? 2 vol(W ) q?2 The statement follows now again by taking the in?mum over all polygons.

13

4

Proof of Theorem 2

Parts (a) and (b) of Theorem 2 have very di?erent proofs. We present them separately. Proof of Theorem 2 (a). We choose a vertex v0 ∈ V and introduce the following functions m, M : F → {0, 1, 2, . . . , ∞}: m(f ) = M (f ) = max{d(w, v0 ) | w ∈ ?f }. min{d(w, v0 ) | w ∈ ?f },

Note that the face f “opens up” at distance m(f ) and “closes up” at distance M (f ) from v0 . We call a face f ?nite, if M (f ) < ∞. The idea of the proof is to “open up” successively every ?nite face f ∈ F into an in?nigon without violating the vertex bound. In this way, we will build up a comparison tree T with the same vertex bound p and satisfying ?(G ) ≤ ?(T ). It turns out, however, that ?nite faces f with more than one vertex in the sphere SM (f ) (v0 ) cause problems in this “opening up” procedure (since the distance relations to the vertex v0 will be changed). Therefore, we ?rst modify the tessellation G by removing all edges connecting two vertices v, w at the same distance to v0 . The modi?ed planar graph is denoted by G0 = (V0 , E0 , F0 ). To keep track, we add at each of the vertices v, w a short terminal edge. These terminal edges do not belong “o?cially” to the graph G0 and serve merely as reminders that an edge can be added in their place without violating the vertex bound of the graph. Moreover, we can only guarantee ?(G0 ) ≥ ?(G ), if these ino?cial edges are included in G0 . (At the end of the procedure we will replace all “ino?cial” terminal edges by in?nite trees rooted in v and w.) The modi?cation G → G0 is illustrated in Figure 2. (For convenience, the vertices belonging to distance spheres Sn (v0 ) are arranged to lie on concentric Euclidean circles around v0 .)

v0

v0

G

G0

Figure 2: Removing edges between vertices on the same spheres and replacing them by “ino?cial” terminal edges 14

Note that none of the distance relations of the vertices in G0 (without the ino?cial terminal edges) to the vertex v0 are changed and that we still have Cut(v0 ) = ?. Moreover, the modi?ed graph G0 (without the ino?cial terminal edges) has a new set of faces F0 . Every ?nite face f of G0 has now even degree, since f opens up at a single vertex in the sphere Sm(f ) (v0 ) and f closes up at a single vertex in the sphere SM (f ) (v0 ). We order all ?nite faces f0 , f1 , f2 , . . . of G0 such that we have M (f0 ) ≤ M (f1 ) ≤ M (f2 ) ≤ ... Next we explain the ?rst step of our procedure, namely, how to open up f0 into an in?nigon f0 . Let n = M (f0 ) ≥ 1 and w ∈ ?f0 such that d(w, v0 ) = n. Since C (v0 ) = ?, we can ?nd an in?nite geodesic ray w0 = w, w1 , w2 , · · · ∈ V such that d(wi , v0 ) = n + i. We may think of v0 as being the origin of the plane and of w0 , w1 , . . . as being arranged to lie on the positive vertical coordinate axis at heights n, n + 1, . . . with straight edges between them. Now we cut our plane along this geodesic ray, i.e., replace the ray by two parallel copies of the ray and thus preventing the face f0 from closing up at distance n. In this way, f0 becomes an in?nigon, which we denote by f0 . (In fact, we rotationally shrink the angle 2π to 2π ? ? around v0 to open up a conic sector of angle ? containing the in?nigon f0 .) The procedure is illustrated in Figure 3. Note that (j ) (2) (1) the vertices wi are replaced by two copies wi , wi , such that wi is connected (1) (j ) to wi+1 for j = 1, 2 and wi inherits all previous neighbors of wi at one side of the ray and wi inherits all previous neighbors of wi at the other side of the ray (this concerns in particular also the “ino?cial” vertices). In this way we obtain a new planar graph G1 = (V1 , E1 , F1 ).
(2)

G0
f0 v0

G1
f0 v0

Figure 3: Changing the ?nite face f0 into an in?nigon f0 The graph G1 is still connected. Note also that we have
(1) |wi |

|w0 | + |w0 | +
(2) |wi |

(1)

(2)

= |wi | + 2,

= |w0 | + 1,

(13) ? i ≥ 1. (14)

After including the ino?cial terminal edges in the graph G1 , we still have |v | ≤ p ? v ∈ V1 ,

and (13), (14) imply that ?(G1 ) ≥ ?(G0 ) ≥ ?(G ). In the second step we carry out the same procedure with the face f1 ∈ F1 , and obtain a new connected planar graph G2 = (V2 , E2 , F2 ), with f1 ∈ F1 15

replaced by the in?nigon f1 ∈ F2 . Again, after including the ino?cial terminal edges, the graph G2 has vertex bound p and satis?es ?(G2 ) ≥ ?(G1 ) ≥ ?(G ). It is now clear how to repeat the procedure. Note that for every radius n ≥ 1 there is a large enough j ≥ 1 such that the graphs Gj , Gj +1 , Gj +2 , . . . remain unaltered inside the balls Bn (Gk , v0 ). This fact guarantees that there is a wellde?ned limiting graph associated to the sequence Gj . This limit is a connected tree T0 (since all faces of T0 are in?nigons). In T0 , we replace now ?nally the ino?cial terminal edges by in?nite trees, rooted at the corresponding proper vertices of the tree T0 , with branching sequence 1, p ? 1, p ? 1, p ? 1, . . . . These in?nite trees can be nicely ?tted into the in?nigons to yield an in?nite planar tree T with vertex bound p and satisfying ?(T ) ≥ ?(G ). Since we obviously have ?(T ) ≤ ?(Tp ) = log(p ? 1), the proof of part (a) of the theorem is ?nished. Proof of Theorem 2 (b). We prove the equivalent curvature version of the statement, given in the remark after the theorem. Since |f | = q < ∞ for all faces f , G is a tessellating plane graph in the sense of [BP1] and we have κ(v ) = 1 ? q?2 |v |. q

Since {κ(v ) | v ∈ V} is a discrete set and bounded from below by ?b, we can 2 assume, without loss of generality, that ?b is of the form 1 ? q? q p, for some integer value p ≥ 3. (In fact, p is the optimal upper bound on the vertex degree of G .) Let Sn , Bn be the combinatorial spheres and balls in G with respect to a reference vertex v0 ∈ V and sn = |Sn |. Corollary 6.4 of [BP1] states that we have 2q (1 ? κ(Bn )). sn+1 ? sn = q?2 Applying this equation twice, we derive sn+2 ? 2sn+1 + sn = ? 2q 2q κ(Sn+1 ) ≤ bsn+1 . q?2 q?2 s1 ≤ p, s0 = 1,

Hence we obtain the following recursion inequality sn+2 ≤ 2τ sn+1 ? sn , with τ = 1 +
q q ?2 b

≥ 1. It is easy to see that the sequence σn+2 = 2τ σn+1 ? σn , σ1 = p, σ0 = 1, (15)

is strictly increasing and dominates the sequence sn . Moreover, σn describes the cardinality of a sphere of radius n in the regular tessellation Gp,q . This implies that ?(G ) ≤ ?(Gp,q ). Now, we return to the sequence σn , as de?ned in (15). We ?rst consider the case τ > 1. The recursion formula implies that σn = u τ ? τ2 ? 1
n

+v τ +

τ2 ? 1

n

,

with constants u, v ∈ R chosen in such a way that the initial conditions are satis?ed. Since 0 < τ ? τ 2 ? 1 < 1, 16

we conclude that v = 0, for otherwise we would have σn → 0, contradicting to the fact that Gp,q is an in?nite graph. Hence, σn behaves asymptotically like σn ? v τ + τ2 ? 1
n

,

with a positive constant v . This, together with (7) implies that ?(Gp,q ) = lim log σn = log τ + n τ2 ? 1 . (16)

n→∞

In the case τ = 1, the sequence (15) is simply given by σn = n(p ? 1) + 1. Linear growth of σn implies that ?(Gp,q ) = 0, which also coincides with (16).

References
[Al] [Ar] N. Alon, Eigenvalues and expanders, Theory of computing (Singer Island, Fla., 1984). Combinatorica 6 (1986), no. 2, 83–96. N. Aronszajn, A unique continuation theorem for solutions of elliptic partial di?erential equations or inequalities of second order, J. Math. Pures Appl. (9) 36 (1957), 235–249.

[BP1] O. Baues, N. Peyerimho?, Curvature and geometry of tessellating plane graphs, Discrete Comput. Geom. 25 (2001), no. 1, 141-159 [BP2] O. Baues, N. Peyerimho?. Geodesics in Non-Positively Curved Plane Tessellations, Advances of Geometry 6, no. 2, (2006), 243-263. [Br] [BS] R. Brooks. A relation between growth and the spectrum of the Laplacian, Math. Z. 178 (1981), 501-508. I. Benjamini, O. Schramm. Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant, Geom. funct. anal. 7, (1997), 403-419.

[Che] J. Cheeger, A lower bound for the lowest eigenvalue of the Laplacian, in: Problems in analysis, asymposium in honor of S. Bochner, Princeton Univ. Press, Princeton, (1970), 195-199. [Chu] F. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, 92. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. [CGY] F. Chung, A. Grygor’yan, S.-T. Yau, Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs, Comm. Anal. Geom. 8 (2000), no. 5, 969–1026. [Do] J. Dodziuk, Di?erence equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794.

17

[DKa] J. Dodziuk, L. Karp, Spectral and function theory for combinatorial Laplacians, Geometry of Random Motion, (R. Durrett, M.A. Pinsky ed.) AMS Contemporary Mathematics, Vol 73, (1988), 25-40. [DKe] J. Dodziuk, W. S. Kendall, Combinatorial Laplacians and isoperimetric inequality, From Local Times to Global Geometry, Control and Physics, (K. D. Elworthy ed.) Longman Scienti?c and Technical, (1986), 68-75. [DL] H. Donnelly, P. Li, Pure point spectrum and negative curvature for noncompact manifolds, Duke Math. J. 46 (1979), no. 3, 497–503. [Fu1] K. Fujiwara, Growth and the spectrum of the Laplacian of an in?nite graph, T? ohoku Math. J. 48 (1996), 293-302 [Fu2] K. Fujiwara, Laplacians on rapidly branching trees, Duke Math Jour. 83, no 1, (1996), 191-202. [GaHuLa] S. Gallot, D. Hulin, J. Lafontaine, Riemannian Geometry, Springer Verlag (1990). [Gri] D. Grieser, The ?rst eigenvalue of the Laplacian, isoperimetric constants, and the max ?ow min cut theorem, Arch. Math. (Basel) 87 (2006), no. 1, 75–85. [Gro] M. Gromov, Hyperbolic groups, Essays in group theory, 75–263, Math. Sci. Res. Inst. Publ., 8, Springer, New York, 1987 [HJL] O. H¨ aggstr¨ om, J. Jonasson, R. Lyons, Explicit isoperimetric constants and phase transitions in the random-cluster model, Ann. Probab. 30 (2002), no. 1, 443-473. [Hi] Y. Higuchi, Combinatorial curvature for planar graphs, J. Graph Theory 38 (2001), no. 4, 220–229.

[HiShi] Y. Higuchi, T. Shirai, Isoperimetric constants of (d, f )-regular planar graphs, Interdiscip. Inform. Sci. 9 (2003), no. 2, 221-228. [Ke] M. Keller, The essential spectrum of the Laplacian on rapidly branching tessellations, arXiv:0712.3816.

[KLPS] S. Klassert, D. Lenz, N. Peyerimho?, P. Stollmann, Elliptic operators on planar graphs: unique continuation or eigenfunctions and nonpositive curvature, Proc. Amer. Math. Soc. 134, (2005), 1549-1559. [KLS] S. Klassert, D. Lenz, P. Stollmann, Discontinuities of the integrated density of states for random operators on Delone sets, Commun. Math. Phys. 241, (2003), 235-243. [KS] M. Kohmoto, B. Sutherland, Electronic states on a Penrose lattice, Phys. Rev. Lett. 56, (1986), 2740-2743. [LV] D. Lenz, I. Veseli? c, Hamiltonians on discrete structures: Jumps of the integrated density of states and uniform convergence, arXiv:0709.2836.

[McK] H. P. McKean, An upper bound to the spectrum of ? on a manifold of negative curvature, J. Di?. Geom. 4, (1970), 359-366. 18

[MW] B. Mohar, W. Woess, A survey on spectra of in?nite graphs, Bull. London Math. Soc. 21, (1989), 209-234. [St] D. A. Stone, A combinatorial analogue of a theorem of Myers and Correction to my paper: ”A combinatorial analogue of a theorem of Myers”, Illinois J. Math. 20 (1976), no. 1, 12–21, and Illinois J. Math. 20 (1976), no. 3, 551–554

[Sull] D. Sullivan, Related aspects of positivity in Riemannian geometry, J. Differential Geom. 25 (1987), no. 3, 327–351. [Sun] T. Sunada, Fundamental groups and Laplacians, Selected papers on number theory, algebraic geometry, and di?erential geometry, 19–32, Amer. Math. Soc. Transl. Ser. 2, 160, Amer. Math. Soc., Providence, RI, 1994. [We] A. Weber, Analysis of the physical Laplacian and the heat ?ow on a locally ?nite graph, arXiv:0801.0812. [Woe] W. Woess, A note on tilings and strong isoperimetric inequality, Math. Proc. Cambridge Philos. Soc. 124 (1998), no. 3, 385–393 [Woe2] W. Woess, Random Walks on In?nite Graphs and Groups, Cambridge Tracts in Mathematics 138, Cambridge University Press, (2000). [Woj] R. K. Wojciechowski, arXiv:0712.1570. Stochastic Completeness of Graphs,

19