MIMS Technical Report No.00007 (200802041)

Proceedings of Symposia in Pure Mathematics

Discrete Geometric Analysis
Toshikazu Sunada
Abstract. This is an expository article on discrete geometric analysis basedon the lectures which the author gave at Gregynog Hall, University of Wales,
as an activity of the Project “Analysis on graphs and its applications” in the
Issac Newton Institute. Topics are selected to illustrate the nature of the
field; that is, we focus upon analysis on graphs with a geometric flavor such asgraph versions of harmonic theory and spectral geometry of Laplacians. Zeta
functions and random walks are also discussed from a geometric viewpoint.

1. Intorduction
Discrete geometric analysis is a hybrid field of several traditional disciplines;
say, graph theory, geometry, theory of discrete groups, and probability. As indicated by the title, this field concerns solely analysis on graphs, a synonym of“1-dimensional cell complex”. Edges in a graph as 1-dimensional objects, however,
do not play a substantial role except when we discuss geometry of graphs. Therefore our view is different from, for instance, the case of quantum graphs where
differential operators on edges are vital. Actually the role of edges in analysis isjust to give a neighboring relation among vertices, and difference operators linked
with this relation stand in for differential operators. We thus do not need to worry
about irregularity of functions which, for differential operators, may cause sometrouble, if not serious. Instead the combinatorial aspect of graphs creates a different kind of technical complication. Furthermore, analysis on both infinite graphs
and non-compact manifolds involves much the same degree of difficulty.
The “protagonist” in our story is a discrete analogue of Laplacians on manifolds(and related operators), which appears in many parts of mathematical sciences. In
the nature of things, ideas cultivated in global analysis provide us a good guiding principle on the one hand, and the practical motivation is the moving force oftheoretical progress on the other. Thus, what a Russian luminary P. L. Chebyshev (1815-1897) maintained in a general context applies to our field; that is, theagreement of theory and practice brings most beneficial results. The aim of thisintroductory article is to summarize an overview of what has been done in discretegeometric analysis for the past few decades. For more comprehensive accounts ofsome specific subjects and related matters, the reader may refer to Colin de Verdièrec0000(copyright holder)

1991 Mathematics Subject Classification. Primary 05-02; Secondary 31C20, 39A12.
Key words and phrases. Graph, Discrete Laplacian, Zeta function.
1

2

TOSHIKAZU SUNADA[31], W. Woess [137] and F. R. K. Chung [24]. See also N. Biggs [13] which deals
with aspect of this field from a similar viewpoint.
2. Discrete harmonic integrals
We shall start with a short historical note on “ harmonic integrals” on graphs
which gives us rudimental ideas involved in the development of discrete geometricanalysis. The story begins with Kirchhoff’s famous work (1845) on resistive circuits, electric networks consisting of resistors alone. What were established by G.
Kirchhoff at the age of twenty-one are the fundamental laws of electric circuits1;
namely the current law and the voltage law, which, in conjunction with Ohm’s law,lead to the existence and uniqueness of steady currents in circuits. His argument
can be effectively interpreted by modern terminology such as chains and cochainson a graph. And so Kirchhoff’s theory is, from a mathematical viewpoint, regarded
as a prototype of algebraic topology for cell complexes which flourished after thefundamental work of Poincaré (1895). Years later came H. Weyl on the stage, afounder of the harmonic theory of manifolds. He observed in 1920s that the protoidea of his far-reaching “method of orthogonal projections” could be applied tothe problem of circuits. This, in fact, reduces the problem to the discrete Poisson
equation ∆f = g (f being an electric potential and g being an external current toflow into the circuit)2.
Leaving the historical remark aside for a while, let us give several basic definitions. The operator ∆ in the discrete Poisson equation above is a special
case of what we call the discrete Laplacian on a weighted graph. Here a graph3
X = (V, E) with a set of vertices V and a set of all oriented edges E is said to beweighted if we are given positive-valued functions mV on V and mE on E satisfyingmE (e) = mE (e) (e being the inverse edge of e). We denote by o(e) (resp. t(e))
the origin (resp. terminus) of an edge e ∈ E. The discrete Laplacian ∆ = ∆X
is defined as d∗ d : C 0 (X, R) −→ C 0 (X, R) where d : C 0 (X, R) −→ C 1 (X, R) is
the coboundary operator of cochain groups; namely C 0 (X,¡ R)¢ = {f
¡ : V¢ −→ R},
C 1 (X, R) = {ω : E −→ R; ω(e) = −ω(e)}, and df (e) = f t(e) − f o(e) . We arethus thinking of d as a graph version of the exterior differentiation. The adjoint d∗
is the one associated with the inner products on C k (X, R) (k = 0, 1) defined by
X
1X
hf1 , f2 i =f1 (x)f2 (x)mV (x), hω1 , ω2 i =ω1 (e)ω2 (e)mE (e).
2
x∈V

e∈E

Obviously the operator ∆ is symmetric and nonnegative. Its explicit shape is
X
£ ¡
¢
¡
¢¤
1
∆f (x) = −mE (e) f t(e) − f o(e)(x ∈ V, f ∈ C 0 (X, R)),mV (x)
e∈Ex

where Ex =P{e ∈ E; o(e) = x}. The Poisson equation ∆f = g has a solution f if
and only if x∈V g(x)mV (x) = 0 since Ker ∆ consists of constant functions, andImage ∆ = (Ker ∆)⊥ . In what follows, we occasionally write C(V ) for C 0 (X, R).
The discrete Laplacian for a resistive electric circuit is the case when mV ≡ 1
and mE (e) is the conductance (the reciprocal of the resistance) of the resistor
1His work was based on a report to the exercises given by his university teacher.
2The same idea applies to circuits consisting of capacitors.

3Graphs are allowed to have loop edges and multiple edges. Unless otherwise stated, graphs
are always supposed to be connected and locally finite.

DISCRETE GEOMETRIC ANALYSIS

3

represented by e. To see why so, note that both current i and voltage v areregarded as 1-cochains which, in view of P
Ohm’s law, are related to each other bymE (e)v(e) = i(e). The current law says e∈Ex i(e) − g(x) = 0, while the voltagePn
law claims that i=1 v(ei ) = 0 for every closed path c = (e1 , . . . , en ) (ei ∈ E)
which is equivalent to say that there exists a f ∈ C(V ) with v = −df (f being
called the electric potential). Thus combining Ohm’s law and Kirchhoff’s laws,
we get the discrete Poisson equation ∆f = g, from which it follows that a steadyflow of electricity takes place if and only if the total amount of currents entering
the circuit from outside is zero. Since the potential f is uniquely determined up to
additive constants, the current (and hence the voltage) is also uniquely determined.
Just for fun, we suggest the reader to prove the following claim due to M. Dehn
(1903) by reducing it to a problem involving the discrete Poisson equation. If a
rectangle K can be divided into finitely many rectangles with rational ratio of two
adjacent sides, then the ratio of two adjacent sides of K is rational (the converse
is trivial). Though the claim itself is hardly more than a puzzle, one can still seesome essence of procedures for transforming from a problem seemingly irrelevant
to graphs to a problem of graphs. A hint will be given at the end of this section.
The notion of discrete Laplacians shows up in the “data points modeling” inCG and CAD (Computer Aided Design)4. The idea is to measure the shape ofa real object by using devices such as a laser scanner or a charge-coupled device(CCD) camera. Digital images from CCD camera are then transmitted to the“digital space” in a computer for reconstruction, storage and analyzation using image processing technique. More specifically, by measuring, we obtain an enormous
number of data points realized in R3 which form a PL (piecewise linear) surface Σin R3 consisting of triangular meshes. What we need to do is to give an explicit
parametrization of Σ by two parameters, say (u, v). We do this by a PL map f , withthe least “distortion”, from Σ into a region in the (u, v)-plane with fixed boundary
values. If we consider the graph X = (V, E) obtained by taking the 1-skeleton of Σ,and think of f as a R2 -valued function on V , then the magnitude of distortion is expressed as h∆f , f i where ∆ is the discrete Laplacian associated with suitable weightfunctions. Thus a discrete analogue of the Dirichlet principle allows us to reduce
the problem to the boundary value problem for the discrete Laplace equation.
We shall formulate the boundary value problem in a slightly general setting.
A subset S ⊂ V is said to be thin if any two vertices x, y ∈ V \S can be joinedby a path not passing through S, and, for any x ∈ S, there exists e ∈ E suchthat o(e) ∈ S, t(e) ∈ V \S. For a thin subset S, which is going to play the roleof boundary, one can prove that, if f satisfies ∆f = 0 on V \S, and if f attains
its maximum (or minimum) on V \S, then f is constant (Maximum principle).
From this, it follows that, if f satisfies ∆f = 0 on V \S and f = 0 on S, thenf = 0. This implies that the linear map T : C(V ) −→ C(V ) defined by (T f )(x) =(∆f )(x) (on V \S), (T f )(x) = f (x) (on S) is injective so that T is an isomorphism.
Therefore, for every g ∈ C(V \S) and h ∈ C(S), the boundary value problem∆f = g (on V \S), f = h (on S) has a unique solution f . Moreover, for a givenh ∈ C(S), critical functions for the functional E(f ) = kdf k2 on the space F = {f ∈C(V ); f |S = h} are those f ∈ F satisfying ∆f = 0 on V \S (Dirichlet principle).
The set-up above of discrete harmonic theory leads us right away to an analogueof the Hodge-Kodaira theorem, which claims that the space H1 (X) of “harmonic
4Due to Yasuhiro Shimizu, Nihon Unisys, Ltd.

4

TOSHIKAZU SUNADA

forms” on X is isomorphic to H 1 (X, R) = C 1 (X, R)/Image d. Here, imitating
harmonic forms on a manifold, we say that a 1-cochain ω ∈ C 1 (X, R) is a harmonic
form if d∗ ω = 0. Although this is again an easy exercise in linear algebra, it is still
useful in some scenes.
Weyl’s idea for electric circuits has been rediscovered by many applied mathematicians even after 1950. Meanwhile, algebraic techniques have been developed
under the name of “algebraic graph theory”, especially since 1974, when the firstedition of N. L. Biggs’ book [14] was published. This concise book is still an
informative source of the field.
One of P
the main objects in this field is the adjacency operator5 defined by(Af )(x) = e∈Ex f (t(e)), which shows up as a principal part of a discrete Laplacian on a graph with mV ≡ 1, mE ≡ 1; say, ∆ = D−A, where Df (x) = (deg x)f (x).
As a sample of results in algebraic graph theory, we bring up the following remarkable identity linking the tree number κ(X) (the number of spanning trees6) andeigenvalues 0 = λ0 < λ1 ≤ · · · ≤ λN −1 (N = |V |) of ∆ = D − A(2.1)

κ(X) = λ1 · · · λN −1 /N.

The proof, which can be found in [14], exhibits an indigenous character of algebraic
graph theory.
The notion of tree numbers originated in the work of A. Cayley (1889) who
tried to count all trees with given N vertices (the answer is N N −2 , which is nothing
but the tree number of the complete graph KN over N vertices). An interesting
aspect of κ(X) is that it appears in various forms in graph theory. For instance, if{c1 , . . . , cn } is a Z-basis of H1 (X, Z), then κ(X) = det(ci · cj )ij where the symbol“·” stands for the inner product in C1 (X, R) defined by e · e0 = 1 (e = e0 ), e · e0 =
−1 (e = e0 ), e · e0 = 0 (otherwise). In other words, the volume of the torus
A(X) = H1 (X, R)/H1 (X, Z) with the flat metric induced from this inner productis equal to κ(X)1/2 .
Another sample is the claim that A has at least diam(X)+1 distinct eigenvalues,
where diam(X) is the diameter of X, the maximal value of the distance function7d(x, y). This is interesting since, in the claim, we see a naive relation between lengthof paths and eigenvalues. The proof actually resorts to a path of the shortest lengthjoining x and y with d(x, y) = Diam(X) and employs the fact that the matrix
element hAn δy , δx i is non-zero if and only if there exists a path of length n joining
x and y, where δx is the characteristic function on V with support {x}. Such a
relation is also seen in the simple fact that tr An is equal to the number of closed
paths of length n. In Section 8, we treat a counting problem of closed paths without
backtracking8, which is more subtle, and is related to A via the trace formula or
the Ihara zeta function. In this connection, the auxiliary operator An defined byX
f (t(c))(An f )(x) =c;geodesic|c|=n,o(c)=x

5When we talk about A, we always assume m

V

≡ 1.

6A spanning tree of X is a subgraph which has no cycles and contains all vertices of X.

7The distance between two vertices x, y is defined to be the the number of edges in the
shortest path joining x and y, which we denote by d(x, y).
8A path c = (e , . . . , e ) is called a path without backtracking (or geodesic) if en1
i+1 6= ei (i =1, . . . , n − 1). If, in addition, c is closed and e1 6= en , then c is said to be a closed path without
backtracking (or closed geodesic).

DISCRETE GEOMETRIC ANALYSIS

5

is useful in the case of regular graphs, where o(c) (resp. t(c)) denotes the origin(resp. terminus) of a path c, and |c| denotes the length of c, i.e., the number ofedges in c. Incidentally, when X is a regular graph9 of degree q + 1, we have therecursion formula A21 = A2 + (q + 1)A0 , A1 An = AX
n+1 + qAn−1 (n ≥ 2). We
also find that the operators T0 = I, T1 = A, Tn =An−2i (n ≥ 2) satisfy0≤i≤n/2

T1 Tn = Tn+1 + qTn−1 (n ≥ 1). We thus have the following identities which willplay an important role later in our discussion (cf. [110]):
(2.2)
(2.3)

∞
X
n=0
∞
X
n=0

An z n =1 − z2,
1 − Az + qz 2

Tn z n =1.
1 − Az + qz 2

The discrete Laplacian D − A is canonical in the sense that it depends only on
the graph structure. Another canonical one showing up frequently is I − D−1 A, thediscrete Laplacian associated with the weight functions mV (x) = deg x, mE ≡ 1.
This is closely related to simple random walks on graphs (see the last section). In
what follows, D − A is said to be the combinatorial Laplacian, and I − D−1 A is
said to be the canonical Laplacian.
The reader already could conceive that discrete geometric analysis forms a small
realm in the “world” of mathematics, which somehow reminds us of Bonsai, thefamous Japanese traditional art of botanical miniature10. But this does not mean
frivolousness of the field since, as will be seen subsequently, it has produced resultsof a surprising variety and depth11.
A Hint to prove Dehn’s theorem12: To construct a weighted graph X = (V, E), we
first orient K by choosing one of its two sides to be “horizontal”. We may assume thatits height= 1. Let a be its width. By setting V =the set of all vertical line segments
appearing in the dissection, E o =the set of all small rectangles, o(e) =the line segment
containing the left side of e. t(e) =the line segment containing the right side of e, we getan oriented graph (V, E o ). Forget the orientation, and put mE (e)=(height of e)/(widthof e), mV ≡ 1. Let x0 and y0 be two vertices representing the left and right sides of K,
respectively, and define the function g ∈ C(V ) by g(x0 ) = 1, g(y0 ) = −1, and g(x) = 0
otherwise. Then ∆f = g has the solution f defined by f (x) =distance between x0 and thevertical line segment x. By the assumption, ∆f = g is transformed to a linear equation
Ax = b with A, b having rational entries The existence of a real solution assures that
this equation has a rational solution, and hence ∆f = g has a rational-valued solution f0 .
Since f − f0 is constant, we conclude that a = f (y0 ) − f (x0 ) is rational.
9|E | is called the degree of x, and is denoted by deg x. If deg x does not depend on x, thenx
X is said to be regular.
10In this art, real plants such as pine and ume (apricot) trees are beautifully and skillfully
miniaturized in a terse style, and their conciseness stirs up our imagination on the real beauty of
their original appearances.
11See the prologue of N. Biggs [13].
12The proof here is a modification of the one due to R. L. Brooks, C. A. B. Smith, A. H.
Stone and W. T. Thutte [15] who reduced the problem to that of electric circuits. The original
proof due to M. Dehn [36] is much more complicated.

6

TOSHIKAZU SUNADA

3. Abel-Jacobi maps in graph theory
The tree number we have mentionedPhas a group theoretic meaning. Indeed,
if we put C 0 (X, Z)0 = {f ∈ C 0 (X, Z);x∈V f (x) = 0}, then¡the equality¢ (2.1)
implies that κ(X) is the order of the finite group C 0 (X, Z)0 /∆ C 0 (X, Z) , where∆ is the combinatorial Laplacian. For example, when X = KN , the group isisomorphic to (ZN )N −2 . This view tempts us to pursue the analogy further. Thistime, we consider graph theoretic
analoguesof algebraic-geometric concepts.
¡¢
The group C 0 (X, Z)0 /∆ C 0 (X, Z) reminds us of the Picard group for a complete algebraic curve13 In algebraic geometry, the Picard group is an abelian variety which is the target of the Abel-Jacobi map, a canonical regular map fromthe curve into Pic. In the case of graphs,¡ taking a¢ reference point x0 ∈ V , wedefine Φ : V −→ Pic(X) = C 0 (X, Z)0 /∆ C 0 (X, Z) by Φ(x) = δx − δx0 , whichis entitled to be called a discrete analogue of Abel-Jacobi maps. It is easily
checked that
harmonic function in the sense that
£ an
¡ abelian-group-valued¢¡¢¤
P Φ is∆Φ(x) = e∈Ex Φ t(e) − Φ o(e) = 0, and is characterized by the following universal property: For any harmonic function ϕ on V with values in an abelian groupG, there exists a unique homomorphism f : Pic(X) −→ G such that ϕ = f ◦ Φ.
The notion of graph theoretic Abel-Jacobi maps above was introduced by R.
Bacher, P. De La Harpe, and T. Nagnibeda [7] in 1997. See also N. L. Biggs [13] for
related topics. In connection with Abel-Jacobi maps, M. Baker and S. Norine [8]recently gave a discrete analogue of the classical Riemann-Roch theorem together
with its application to a certain chip-firing game played on the vertices of a graph.
There is another version of Abel-Jacobi maps in graph theory ([80],[81]). Recall
Abel’s theorem which claims ¡that the¢∗ Picard group of a curve S is identified with
the Jacobian (torus) J(S) = Ω1 (S) /H1 (S, Z) where Ω1 (S) denotes the space of1∗holomorphic 1-forms on S, and we
Z think of H1 (S, Z) as a subgroup of (Ω (S)) by
using the paring map ([α], ω) =

ω. In terms of the Jacobian, the Abel-Jacobiαmap Φ : S −→ J(S) turns out to be the map defined by the paring
Z x
(3.1)
(Φ(x), ω) =ω (mod H1 (S, Z)).
x0

Having this in mind, we define a map Φ : V −→ H1 (X, R)/H1 (X, Z) in the following
way. Let X ab = (V ab , E ab ) be the maximal abelian covering graph14 over X; in otherwords, X ab is the covering graph over X with the covering transformation group
H1 (X, Z). Let P : C1 (X, R) −→ H1 (X, R) = Ker ∂ be the orthogonal projection.
ab
Fix a reference point x0 ∈ V ab , and let ec = (ee1 , . . . , ef
withn ) be a path in Xe 0 ) = 0 ando(ec) = x0 , t(ec) = x. Then put Φ(xeΦ(x)= P (e1 + · · · + en ) = P (e1 ) + · · · + P (en ),e is well-defined; namely,
where ei ∈ E is the image of eei by the covering map. The Φee is completely
Φ(x)is independent of the choice of ec. It should be noted that Φabeedetermined by {P (e)}e∈E . We extend Φ to X as a piecewise linear map. Then Φ
13For an algebraic curve S, the Picard group is defined as Div0 (S)/Prin(S) where Div0 (S)is the group of divisors with degree 0, and Prin(S) is the group of principal P
divisors which aredivisors of non-zero meromorphic functions on S. Note that ∆ log |f | = 2π
ordp (f )δp for ameromorphic function f .
14Also called the universal homology covering graph.

DISCRETE GEOMETRIC ANALYSIS

7ee + σ for σ ∈ H1 (X, Z). Therefore Φe induces a map Φ : X −→satisfies Φ(σx)= Φ(x)1
H1 (X, R)/H1 (X, Z). We may check that, for ω ∈ H (X),(Φ(x), ω) = ω(e1 ) + · · · + ω(en )(mod H1 (X, Z)),in which the reader may feel a flavor of Abel-Jacobi maps defined by (3.1).
The flat torus A(X) = H1 (X, R)/H1 (X, Z) introduced in the previous section
is called the Albanese torus, and Φ : X −→ A(X) is said to be the Albanesemap. To see a relation between Abel-Jacobi maps and Albanese maps, note thatthe homology group H1 (X, Z) is an integral lattice in H1 (X, R) in the sense thatα · β ∈ Z for α, β ∈ H1 (X, Z). Therefore the dual lattice H1 (X, Z)# = {α ∈H1 (X, R); α · β ∈ Z for every β ∈ H1 (X, Z)} contains H1 (X, Z). The discrete
Albanese torus A(X), a finite subgroup of A(X), is defined to be the quotientgroup H1 (X, Z)# /H1 (X, Z). It is verified that Φ(V ) ⊂ A(X), and that A(X) is
isomorphic to Pic(X) in a canonical way (an analogue of Abel’s theorem). Under
the identification A(X) = Pic(X), the Albanese map as a map of V into A(X)coincides with the Abel-Jacobi map.
The inner product on H1 (X, R) induces a nondegenerate symmetric bilinear
form on A(X) with values in Q/Z. Thinking of this form as an analogue of “polarization”, one may ask whether the Torelli type theorem holds in the discrete realm.
More specifically, one asks whether two regular graphs X1 and X2 with the same
degree are isomorphic when there exists a group isomorphism between A(X1 ) andA(X2 ) preserving polarizations15.
The Albanese map is a special harmonic map of the graph X (as a singular
Riemannian space) into the flat torus A(X), which, together with the flat metric, ischaracterized by the minimizing property for a certain energy functional (see [82]for the detail, and [74] for harmonic maps of graphs into metric spaces). As wewill see in the last section, the Albanese map (and its generalization) ties in withan asymptotic property of simple random walks on a crystal lattice.
e to illustrate that Albanese maps are related
Let us give two examples of Φ
to “crystals with big symmetry”. In general, a crystal in mathematical sense is agraph realized in space having periodicity with respect to a lattice group action bytranslations (thus ignoring the physical characters of atoms and atomic forces in a
crystal which may be different one by one). We consider the graphs (A) and (B) in
Figure 1. The graph (B) is nothing but the complete graph K4 .
(A) Take three paths c1 = (e0 , e1 ), c2 = (e0 , e2 ), c3 = (e0 , e3 ), which constitutea Z-basis of H1 (X, Z) satisfying kc1 k2 = kc2 k2 = kc3 k2 = 2, ci · cj = 1 (i 6= j).
Then
1
1
1
3
1
1
P (e0 ) = c1 + c2 + c3 , P (e1 ) = − c1 + c2 + c3 ,
4
4
4
4
4
4
1
3
1
1
1
3
P (e2 ) = c1 − c2 + c3 , P (e3 ) = c1 + c2 − c3 .
4
4
4
4
4
4
e ab ) turns out to be the diamond crystal, which describes the arThe image Φ(Xrangement of carbon atoms (corresponding to vertices) together with the bonding(corresponding to edges) in diamond. The diamond crystal is a join of the samehexagonal rings (the chair conformation in chemical terminology). One observes
that 12 hexagonal rings gather at each vertex.
15This problem was suggested by Kenichi Yoshikawa. If we would remove the conditions on
degree and polarizations, there are many examples of X1 , X2 with A(X1 ) ∼= A(X2 ) ([7]).

8TOSHIKAZU SUNADA

Figure 1(B) Take three closed paths c1 = (e2 , f1 , e3 ), c2 = (e3 , f2 , e1 ), c3 = (e1 , f3 , e2 ) in
K4 , which constitute a Z-basis of H1 (K4 , Z) satisfying kc1 k2 = kc2 k2 = kc3 k2 = 3,
ci · cj = −1 (i 6= j). Then
1
1
1
1
1
1
P (e1 ) = − c2 + c3 , P (e2 ) = c1 − c3 , P (e3 ) = − c1 + c2 ,
4
4
4
4
4
4
1
1
1
1
1
1
P (f1 ) = c1 + c2 + c3 , P (f2 ) = c1 + c2 + c3 ,
2
4
4
4
2
4
1
1
1
P (f3 ) = c1 + c2 + c3 .
4
4
2
ab
e
The image Φ(X) is what we call the K4 crystal (see Remark below). The K4
crystal is a web of the same decagonal rings, and the number of decagonal rings
passing through each vertex is 15.
The two crystals above share two remarkable properties. Firstly, they havemaximal symmetry in the sense that every automorphism as abstract graphs extends
e ab ) has always maximal symmetry for
to a congruent transformation (actually Φ(Xevery X). Secondly they have the strong isotropic property. Here a graph is said
to have the strong isotropic property if it is regular as a graph, say, of degree n,
and if, for any x, y ∈ V and for any permutation σ of {1, 2, . . . , n}, there exists anautomorphism g such that gx = y and gei = fσ(i) where Ex = {e1 , . . . , en }, Ey ={f1 , . . . , fn }. One can prove that a crystal in space (R3 ) with these two properties
is either the diamond crystal or the K4 crystal (and its mirror image)16 ([127]).
Remark. The author learned from Stephen T. Hyde, just after the publicationof [127], that the structure of the K4 crystal has been known in crystallography,
and that the first description of the structure goes back to a pioneer of the area,
A. Wells [135], who called it “(10,3)-a”. M. O’Keeffe and his colleagues [37] havediscussed this structure in some details and renamed it “srs” due to its chemical
relevance. See also [108], [72] and [38] for related matters.
4. Discrete spectral geometry
So far we have traced the history along one stream in discrete geometric analysis. Meanwhile, steady progress has been made in spectral geometry since 1960s,
16The K crystal has chirality while the diamond crystal does not.
4

DISCRETE GEOMETRIC ANALYSIS

9which gave rise to new motivation in graph theory, and provided us with many
concepts in finite and infinite graphs ([40], [41]).
A typical example of such concepts is Cheeger constants, a sort of “isoperimetric” constants introduced by J. Cheeger in 1970 ([23]). The Cheeger constant fora weighted finite graph X = (V, E) is defined byon m (∂ A)
E E; A ⊂ V, A 6= ∅, mV (A) ≤ (1/2)mV (V ) ,(4.1)
h = infmV (A)
where ∂E A = {e ∈ E; o(e) ∈ A, t(e) 6∈ A}. We further put
X1
k = supmE (e).
x∈V mV (x)e∈Ex

2Then we have λ1 ≥ h /2k which is mimicry of the Cheeger inequality (J. Dodziuk[40], N. Alon [3]). Actually, the discrete setting allows us to prove the following
sharper inequality (F. R. K. Chung [26], K. Fujiwara [46]).
p(4.2)
λ1 ≥ k − k 2 − h 2 .
To outline the proof, we start with the following inequality
1X(4.3)
mE (e)|f (t(e))2 − f (o(e))2 | ≤ kdf k(2kkf k2 − kdf k2 )1/2 .
2e∈EThis is an easy consequence of the Schwartz inequality, and holds for any function
f . The crucial part of the proof is in showing that, if V+ = supp f 2 satisfies
mV (V+ ) ≤ (1/2)mV (V ), thenX
(4.4)
mE (e)|f (t(e))2 − f (o(e))2 | ≥ 2hkf k2 .
e∈E

For this sake, we put
E0 = {e ∈ E; f (o(e))2 = f (t(e))2 }, E1 = {e ∈ E; f (o(e))2 > f (t(e))2 },g(V ) = {β0 , β1 , . . . , βr } with 0 = β0 < β1 < · · · < βr ,{e ∈ E1 ; f (o(e))2 = βi and f (t(e))2 = βk }a``Then E = E1 Ē1 E0 , E1 =Eik andEik=(i > k).

i>k
r
X
X X
1X
mE (e)|f (t(e))2 − f (o(e))2 | =(βl − βl−1 )mE (e).
2e∈Ek<l≤i e∈Eik

l=1

2

Put Li = {x ∈ VS; f (x) ≥ βi } (0 ≤ i ≤ r), and note that V = L0 ⊃ L1 ⊃· · · ⊃ Lr . Since k<l≤i Eik = {e ∈ E; o(e) ∈ Ll , t(e) 6∈ Ll } = ∂E Ll , we have
P
P
k<l≤i
e∈Eik mE (e) = mE (∂E Ll ). Noting that mV (Ll ) ≤ mV (L1 ) = mV (V+ ) ≤(1/2)mV (V ) for all l ≥ 1, we have mE (∂E Ll ) ≥ h · mV (Ll ). ThereforerX
1X
mE (e)|f (o(e))2 − f (t(e))2 | ≥ h(βl − βl−1 )mV (Ll ).
2
e∈E
l=1
`
`
`
2
Since
∈ Li − Li+1 , and V = LP
(Lr−1 − Lr ) . . . (L1 −r` f (x) = βi for x P
rL2 ) (L0 − L1 ), we find l=1 (βl − βl−1 )mV (Ll ) = x∈V f (x)2 mV (x). HenceX
1X
mE (e)|f (o(e))2 − f (t(e))2 | ≥ hf (x)2 mV (x) = hkf k2 .
2
e∈E

x∈V

10

TOSHIKAZU SUNADAThe next step is to construct a specific function f satisfying the conditonmV (V+ ) ≤ (1/2)mV (V ). For this end, take a nonzero eigenfunction ψ for λ1 ,and put V + = {x ∈ V ; ψ(x) > 0}, V − = {x ∈ V ; ψ(x) < 0}. Then V + 6= ∅and V − 6= ∅. Without loss of generality, we may assume mV (V + ) ≤ (1/2)mV (V ).
Then the function f defined by f (x) = ψ(x) (x ∈ V + ), f (x) = 0 (x 6∈ V + ) satisfies obviously our condition so that we may put (4.3) and (4.4) together to obtainhkf k2 ≤ kdf k(2kkf k2 − kdf k2 )1/2 . Hence α = kdf k2 /kf k2 satisfies h2 ≤ α(2k − α),from which the inequality α ≥ k − (k 2 − h2 )1/2 follows.
The final step is to see that the function f above satisfies the inequality kdf k2 ≤λ1 kf k2 . This is shown by a tedious but elementary computation. We have thus
obtained the desired inequality λ1 ≥ α ≥ k − (k 2 − h2 )1/2 .
We also have the inequality λ1 ≤ 2h which is viewed as an analogue of Buser’s
inequality in spectral geometry ([21]), and is much easier to show than the lower
bound above. In fact, if we take a subset A such that h = mE (∂E A)/mV (A) andmV (A) ≤ (1/2)mV (V ), and put mV (A) = a and mV (Ac ) = P
b, then the function
defined by f (x) = b (x ∈ A) and f (x) = −a (x ∈ Ac ) satisfies x∈V f (x)mV (x) =0, kf k2 = mV (A)mV (Ac )mV (V ), and kdf k2 = mE (∂E A) (mV (V ))2 . Therefore,
using the following characterization of λ1()
X
kdf k2(4.5)
λ1 = inf; f ∈ C(V ) such thatf (x)mV (x) = 0 ,
kf k2
x∈V

we obtain
λ1 ≤mE (∂E A)mV (V )mE (∂E A)
kdf k2
=
≤2
= 2h.
2
c
kf k
mV (A)mV (A )mV (A)The Cheeger inequality for the case mV ≡ 1, mE ≡ 1 is linked to the theory ofcommunication networks and computer science. A network is a system consistingof an enormous number of nodes (each node represents an individual) and cables(such as telephone lines). Foremost among problems in this theory is to construct(in an explicit way) a graph with the least number of edges such that every subset ofvertices has the most number of distinct neighbors. This is because we would like tominimize the cost of the network by reducing the number of cables and to minimize
the transmission time needed for all individuals to receive information from a few
individuals. Cheeger’s and Buser’s inequalities tell us that the bigger the first
positive eigenvalue λ1 of the combinatorial Laplacian ∆ is, the more efficient the
network is, and vice versa17. This observation leads us to the notions of expanders
and Ramanujan graphs.
An infinite family of finite graphs {Xn }∞n=1 with |Vn | → ∞ as n → ∞ issaid to be a family of expanders if Xn ’s have bounded degree and there exists a
positive constant c with λ1,n ≥ c for the first positive eigenvalue λ1,n of ∆Xn . A√
regular graph of degree q + 1 is said to be a Ramanujan graph if Λ(X) ≤ 2 q
where Λ(X) = max{|µi |; µi is an eigenvalue of the adjacency operator and |µi | 6=
q + 1}18. Obviously an infinite family of Ramanujan graphs with a fixed degree
17This was pointed out first by N. Alon [3] and N. Alon and V. D. Milman [4]. The Cheeger
constant is essentially the same as the magnifying constant which represents the degree of efficiency
of a network.
18q + 1 is always an eigenvalue, while −(q + 1) is an eigenvalue if and only if X is bipartite.
Here a graph is said to be bipartite if one can paint the vertices by two colours in such a way thatany adjacent vertices have different colours.

DISCRETE GEOMETRIC ANALYSIS

11

is a family of expanders. Thus our task is to construct a family of expanders or
preferably a family of Ramanujan graphs with a fixed degree19. The reason why√
the quantity 2 q comes up in the definition of Ramanujan graphs is that, for any
infinite family {Xn } of regular graphs of degree q + 1, we have√
(4.6)
lim inf Λ(Xn ) ≥ 2 q,n→∞which implies that it is impossible to construct an infinite family {Xn } with Λ(Xn )√≤ 2 q − ² (² > 0). An explicit construction of a family of Ramanujan graphs,
which is by no means trivial, was given by A. Lubotzky, R. Phillips and P. Sarnak[90]. They showed that the Cayley graph associated with the group P GL2 (Z/pZ)(or P SL2 (Z/pZ)) and a suitable set of generators is Ramanujan. Their proof relies
heavily on the theory of automorphic forms and the classical Ramanujan conjecture(see the end of Section 7, and [105]). Lubotzky [91] gives a recipe relying on the
representation theory of SL2 (Qp ). See also A. Terras [129] for other examples inwhich the notion of finite symmetric spaces is introduced. As for expanders, see J.
Bourgain and A. Gamburd [20] for instance20. They showed, among other things,
that, given a subset A of SL2 (Z), Cayley graphs X(SL2 (Z/pZ), Ap ) constitute afamily of expanders as p → ∞ if and only if the subgroup hAi of SL2 (Z) generated
by A does not contain a solvable subgroup of finite index. Here Ap is the image in
SL2 (Z/pZ) of A (see Section 7 for the definition of Cayley graphs).
Thus far, we have confined ourselves to a special topic in discrete spectral
geometry. There are, of course, other topics of interest which also fall under thesame title. Let us list some of them.
(1) The notion of diameters is also important in the theory of communication
networks since it is related to the transmission time of information. There are many
articles handling spectral diameter estimates. For example, see N. Alon and V.D.
Milman [4]. F. R. K. Chung, V. Faber and T. A. Manteuffel [28] and P. Sarnak[105] derived the following upper bound on the diameter,diam(X) ≤arccosh(N − 1)¡
¢ + 1.
arccosh (q + 1)/Λ(X)A partial improvement of this bound was given by G. Quenell [103].
(2) The graph version of Courant’s celebrated Nodal Domain Theorem wasestablished by E. B. Davies, G. M. Gladwell, J. Leydold and P. F. Stadler [35]. The
problem is to count the number of nodal domains of an eigenfunction21. Remember
that, in the continuous setting, a nodal domain of a continuous function is defined
to be a connected component of the complement of f −1 (0). A crucial point in
the discrete setting is to find a reasonable formulation for nodal domains because
a function on a graph can change the sign without having zero. For the recent
development, see G. Berkolaiko [12] and R. Band, I. Oren, and U. Smilansky [9].
(3) Two finite graphs are said to be isospectral if they have the same eigenvalues with the same multiplicities. The first example of non-isomorphic isospectral
graphs for the Laplacian D − A was given by L. Collatz and U. Sinogowitz [32].
19

The first example of Ramanujan graphs appeared implicitly in Y. Ihara [69].

20An explicit construction dates back to the pioneer work by G. A. Margulis [92].

21This question started with Sturm’s oscillations theorem which states that a vibrating string
is divided into exactly n nodal intervals by the zeros of its n-th mode of vibrations.

12

TOSHIKAZU SUNADA

See [34] for more examples. The group theoretic method for constructing isospectral manifolds [121] can be exported to the discrete case (see R. Brooks [19] forinteresting discussion).
5. Spectra of infinite graphs
In the case of an infinite weighted graph, we have, in general, the continuous
spectrum which may make the spectral problem more complicated. As a matter offact, much has not yet been explored in the general setting. However as far as thebounds of the spectrum are concerned, the ideas in the previous section work well.
W denote by σ(T ) the spectrum of a hermitian operator T acting in a Hilbert
space. We shall make use of the following notations
X`2 (V ) = {f ∈ C(V ); kf k2 :=f (x)2 mV (x) < ∞},x∈V`2 (E) ={ω ∈ C(E); ω(e) = −ω(e), kωk2 :=1X
ω(e)2 mE (e) < ∞},2e∈E

and we restrict ourselves to the class of weighted graphs satisfying the conditionX1mE (e) < ∞,k = supx∈V mV (x)e∈Exunder which ∆ extends to a hermitian operator of `2 (V ). The Cheeger constant hfor the infinite graph22 is defined by(5.1)

h = infA⊂V

mE (∂E A),
mV (A)

where the infimum is taken over all finite subsets A of V . With this h, two inequalities (4.3), (4.4) hold for every function f on V with finite support. Indeed,
if we look at that part in the proof of the inequality (4.4) where the constant hshows up, then we find that an arbitrary function f satisfies (4.4) because the condition mV (A) ≤ (1/2)mV (V ) is removed in the definition of h above. Thereforek − (k 2 − h2 )1/2 ≤ kdf k2 /kf k2 ≤ k + (k 2 − h2 )1/2 . This implies(5.2)σ(∆) ⊂ [k − (k 2 − h2 )1/2 , k + (k 2 − h2 )1/2 ].

We also have inf σ(∆) ≤ h since the defining function f = χA of a subset A satisfies
kf k2 = mV (A), and kdf k2 = mE (∂E A). In particular, inf σ(∆) = 0 if and only if
h = 0.
In the case of ∆ = D − A on the regular tree of degree q + 1, we have k = q + 1√√
and h = q − 1, and hence σ(∆) ⊂ [q + 1 − 2 q, q + 1 + 2 q]. This is equivalent to√ √σ(A) ⊂ [−2 q, 2 q]. Therefore the estimate above is sharp.
The Cheeger constant at infinity h∞ , which is related to the essential spectrum
σess (∆), is defined as follows. For a finite subset K of V , we put
X1k(K) = supmE (e),x∈K c mV (x)e∈Ex¾½
mE (∂E A); A ⊂ V, |A| < ∞, and A ∩ K = ∅ .
h(K) = inf
mV A
22This is a discrete analogue of the one for open manifolds (R. Brooks [17]).

DISCRETE GEOMETRIC ANALYSIS

13

We then put h∞ = supK⊂V h(K), k∞ = inf K⊂V k(K) (note h ≤ h∞ ≤ k∞ ≤ k).
2
2
It is shown (K. Fujiwara [46]) that σess (∆) ⊂ [k∞ − (k∞− h2∞ )1/2 , k∞ + (k∞−2 1/2h∞ ) ], and inf σess (∆) ≤ h∞ . In particular, if h∞ = k∞ , then σess (∆) = {k∞ }(the converse is also true). As a corollary, one can show that, if X is a rapidly
branching tree in the sense that supK⊂V inf x∈K c deg x = ∞, then σ(∆)\{1} consistsof eigenvalues with finite multiplicity23 for the canonical Laplacian ∆ = I − D−1 A.
We shall mention a few more results.
(1) For ∆ = I − D−1 A, inf σ(∆) + sup σ(∆) ≥ 2 ([64]).
(2) For ∆ = I −D−1 A, sup σess (∆) ≥ 1+2d−1∞ , where d∞ = inf K supx∈K c deg x([61]). In particular, if supx∈V deg x = M (< ∞), then sup σess (∆) ≥ 1 + 2M −1 .
(3) The line graph construction yields infinite graphs with many isolated eigenvalues ([112]).
(4) Let Bn (x0 ) = {x ∈ V ; d(x, x0 ) ≤ n} be the ball with radius n with respect
to the graph distance d, and let bn = mV (Bn (x0 )). Define the growth rate of X by
1/nb = lim supn→∞ bn (≤ ∞), which does not depend on the choice of x0 . One mayeasily prove the inequality b ≥ k −1 h + 1. Under the condition mV (V ) = ∞, thefollowing inequality was established by K. Fujiwara [47] for the canonical Laplacian2.
b1/2 + b−1/2This inequality improves several previous results given by J. Dodziuk and L. Karp[42] and Y. Ohno and H. Urakawa [100]. Actually estimate (5.3) is sharp since theequality holds for the regular tree.
(5.3)

inf σess (∆) ≤ 1 −6. Covering graphs
The proof of inequality (4.6) due to Allon and Boppana relies on the fact thatthe universal covering graph over a regular graph is a regular tree, and that the√ √spectrum of the adjacency operator on the regular tree of degree q+1 is [−2 q, 2 q].
This example leads us to a herd of problems about spectra of covering graphs overmore general finite graphs. Another motivation stems from the spectral study ofCayley graphs which are nothing but regular covering graphs over bouquet graphs24.
Consider a regular covering map X −→ X0 = (V0 , E0 ) over a finite weighted
graph, and let G be the covering transformation group. Lifting the weight functions
on X0 makes X a weighted graph. Our concern is the spectrum of ∆X . It is observed
that, if G is of infinite order, then there exist no eigenvalues with finite multiplicity
so that σess (∆X ) = σ(∆X ).
A tool to treat this situation is twisted Laplacians. Given a unitary representation ρ : G −→ U (H) on a Hilbert space H, we set `2 (ρ) = {f ; V −→ H; f (gx) =ρ(g)f (x)}, which has a natural Hilbert space structure. The twisted Laplacian∆ρ (resp. the twisted adjacency operator Aρ ) is defined to be the restriction to`2 (ρ) of the discrete Laplacian (resp. adjacency operator) acting on H-valued functions. One can establish the following estimates for the bottom of the spectrum
λ0 (ρ) = inf σ(∆ρ ) from below and above(6.1)

c1 δ(ρ, 1)2 ≤ λ0 (ρ) ≤ c2 δ(ρ, 1)2 .

23This is regarded as a discrete analogue of the result due to H. Donnelly and P. Li [43].

24A bouquet graph is a graph with a single vertex and several loop edges.

14

TOSHIKAZU SUNADA

Here c1 , c2 are positive constants independent of ρ (see [125], [128]). The quantityδ(ρ, 1) is the Kazhdan distance between ρ and the trivial representation 1 definedby δ(ρ, 1) = inf{supg∈A kρ(g)v − vk; v ∈ H, kvk = 1}, where A is a finite set ofgenerators of G. (6.1), in particular, says that λ0 (ρ) = 0 if and¡ only if¢δ(ρ, 1) = 0.
Applying this to the regular representation25 ρH : G −→ U `2 (H\G) associatedwith a subgroup H of G, we conclude that λ0 (∆H\X ) = 0 if and only if δ(ρH , 1) = 0
since ∆ρH is unitarily equivalent to the discrete Laplacian ∆H\X on the quotientgraph H\X 26. In particular, since δ(ρG , 1) = 0 if and only if G is amenable27 (cf.
R. J. Zimmer [138]), we find that λ0 (∆X ) = 0 if and only if G is amenable. Thisis a discrete analogue of a result due to R. Brooks [16].
Another effective use of (6.1) is seen in a construction of a family of expanders
by means of a tower of covering graphs. For a fixed finite graph X0 , let · · · → Xn →· · · → X1 → X0 be a sequence of finite-fold covering maps. Suppose that every
covering map Xn −→ X0 is a subcovering map of a fixed regular covering map
X −→ X0 . If the covering transformation group G satisfies the (Kazhdan) property(T), then there exists a positive constant c such that λ1 (Xn ) ≥ c for every n. Here
G is said to have the Kazhdan property (T) (or to be a Kazhdan group) if there
exists a positive constant c such that δ(ρ, 1) ≥ c for every non-trivial irreducible
representation ρ of G ([138]).
As for the property (T), A. Zuk [139] gave an interesting criterion in termsof the smallest positive eigenvalue of a discrete Laplacian defined on a finite set ofgenerators. A typical example of Kazhdan groups is SLn (Z) (n ≥ 3). The rotation group SO(n) (n ≥ 5) has a finitely generated dense Kazhdan subgroup. This
fact has been used to solve Ruziewicz’s problem of the uniqueness of rotationallyinvariant finitely additive measures defined on Lebesgue sets on S n−1 (G. A. Margulis [93] and D. Sullivan [118]). The proof of uniqueness reduces to the existenceof an ²-good set in SO(n), where a finite set A ⊂ SO(n) said
Z to be an ²-good
set if kLa f − f k2 ≥ ²kf k2 for a ∈ A and f ∈ L2 (S n−1 ) withg = 0. Here
S n−1

La f (x) = f (a−1 x). One easily infers that, if the group G generated by A is dense
in SO(n) and has the property (T), then A is an ²-good set for some ² > 0. The
uniqueness also holds for S 2 and S 3 (V. G. Drinfeld [44]). Although this problem is seemingly unrelated to an explicit construction of Ramanujan graphs, bothproblems can be solved using similar methods. See [105] and [91] for details28.
Useful for the study of spectra (in principle at least) is the notion of (integrated) densities of states, which was originally introduced in quantum physics andquantifies how closely packed energy levels are in a quantum-mechanical system.
To define it in our setting, we start with the notion of G-trace. For a G-equivariantGbounded operator T : `2 (V ) −→ `2 (V ) on a regular covering graph X → X0 over a29
finite graph, we define the G-trace of T (cf. Atiyah [5]) byX
X
trG T =mV (x)−1 hT (δx ), δx i =t(x, x)mV (x),
x∈F

x∈F

25ρ

G
H is the induced representation IndH (1) of the trivial representation.

26This implies that, if ρ

H1 and ρH2 are equivalent for two subgroups H1 , H2 , then ∆H1 \Xand ∆H1 \X are unitary equivalent. This gives a method to construct isospectral graphs.
27This is equivalent to that G has an invariant mean.
28The uniqueness breaks down for S 1 .
29The G-trace is a special case of von Neumann traces in operator algebras.

DISCRETE GEOMETRIC ANALYSIS

15

where F is a fundamental set in V for
P the G-action, and t(x, y) stands for the
kernel function of T ; namely T f (x) = y∈V t(x, y)f (y)mV (y). Suppose that T isZ ∞λdE(λ) be the spectral resolution of T . The integrated
hermitian, and let T =−∞density of states for T is defined by ρT (λ) = trG E(λ). Evidently the function ρTis non-decreasing, right-continuous and σ(T ) = supp dρT .
Again let X → · · · → Xn → · · · → X1 → X0 be a tower of finite-fold subcovering graphs over X0 . We denote by Gn the covering transformation group of thecovering map π : X −→ Xn . Suppose that t(x, y) has finite support as a function
on G\(X × X) (note that t(σx, σy) = t(x, y) for every σ ∈ G). Then for each n,
there exists a unique Tn : C(Vn ) −→ C(Vn ) such that (Tn f ) ◦ π = T (f ◦ π) forf ∈ C(Vn ) (for instance, Tn = ∆Xn for TZ = ∆X ). Let {λk } be the eigenvalue ofX
Tn , and define the measure dρn on R by
f dρn =f (λk ). We then have
(6.2)

R

k

−1

dρn = dρT ,w- lim |G/Gn |n→∞Tprovided that n Gn = {1}. This justifies the name “(integrated) density of states”
for ρT . The proof relies on the following “pretrace formula”30 for a G-equivariant
operator S
X X
(6.3)
tr S0 = trG S +s(gx, x)mV (x).
g6=1∈G x∈F

See [126] for the idea, and [49] for a generalization to nonregular covering graphs31.
In case G is an abelian group of infinite order, the covering graph X is calleda crystal lattice, an abstraction of a crystal. This being the case, the unitaryequivalence between ∆X and ∆ρG and the irreducible decomposition of ρG yieldb
the direct integral decomposition over the unitary character group G:Z ⊕∆X =∆χ dχ.
b
G

This is substantially the Bloch-Floquet theorem applied to discrete Laplacians. Let
0 ≤ λ0 (χ) ≤ λ1 (χ) ≤ · · · ≤ λN −1 (χ) be the eigenvalues of ∆χ . Then each λi is ab In particular, theb and σ(∆X ) = SN −1 {λi (χ); χ ∈ G}.
continuous function on G,
i=0
spectrum has a band structure in the sense that σ(∆X ) is the union of N closed
intervals, some of which possibly overlap. It is an interesting problem to find thenumber of gaps in the spectrum. An extreme situation is the case of the maximalabelian covering graph X over a finite graph. In this case, Yu. Higuchi and T.
Shirai [64] proved that there is no gap for the canonical Laplacian ∆ = I − D−1 A
provided that the degree is even. Their proof relies on the famous solution to
the puzzle of the Königsberg bridges due to Euler. Actually, one may constructa one-parameter family of unitary characters χt such that a branch of perturbed
eigenvalues {λi (χt )} covers the whole interval [0, 2]. Such χt is obtained by using aclosed path (Euler path) in X0 such that every unoriented edge appears in it onceand only once. We conjecture that no-gap phenomenon holds for regular graphs of
odd degree as well (see [65]).
30(6.3) is formally transformed to the identity tr S

0 =P[g]∈[G] trGg (gS), where [G] is theset of conjugacy classes, and Gg denotes the centralizer of g in G.
31In [49], dρ is called the Kesten measure.
T

16

TOSHIKAZU SUNADA

For a general abelian covering graph, one may introduce the notions of Blochvarieties and Fermi surfaces which have something to do with an integral representation of the Green kernel (cf. [87]). One can also consider twisted operators
associated with real characters, which are not hermitian any more, but useful when
we explore asymptotic behaviors of random walks on crystal lattices (see the lastsection, and [89] for nilpotent coverings).
7. Cayley graphs
It is worthwhile to treat the case of Cayley graphs separately as group structures
are more directly reflected in the spectra. Here we restrict ourselves to the notionof cogrowth introduced by R. I. Grigorchuk [48]32.
First we shall fix our terminology. Let G be a group, and i : A −→ G be amap of a finite set A into G such that i(A) generates G. We put q = 2|A| − 1. Let
A = {a; a ∈ A} be a disjoint copy of A. A word with letters in A means either void(denoted by ∅) or a finite sequence w = (b1 , . . . , bn ) with bi ∈ A ∪ A. The length
n of a word w = (b1 , . . . , bn ) is denoted by |w| (|∅| = 0). A word w = (b1 , . . . , bn )is said to be reduced if bi+1 6= bi (i = 1, . . . , n − 1), where a is understood to be a.
Denote by g(w) ∈ G the product i(b1 ) · · · i(bn ) (g(∅) = 1), where i(a) is understood
to be i(a)−1 .
The Cayley graph X(G, A) is defined as follows33. The set V of vertices is justG. Oriented edges are the pairs (g, a), g ∈ G, a ∈ A. The origin and terminus of
the edge (g, a) are defined to be g and gi(a), respectively. Forgetting orientation,
we get a connected regular graph X(G, A) of degree q +1. The graph X(G, A) has anatural free G-action. Thus given a subgroup H of G, one can consider the quotientgraph H\X(G, A), called the Schreier graph, whose vertices are right cosets of H.
The adjacency operator on X(G, A) is simply expressed as
X£ ¡
¢
¡
¢¤
Af (g) =f gi(a) + f gi(a)−1 .
a∈A
2

2

A : ` (G) −→ ` (G) is G-equivariant.
£ ¡ that¢ the¡ twisted¢¤ adjacency operator
P NoteAρ is identified with the operator a∈A ρ i(a) + ρ i(a)−1 acting in H, whichis called the Hecke operator associated with ρ.
We define the cogrowth sequence {`n }∞n=0 of (G, A) by¯¯¯`n = {w; w is a reduced word over A with g(w) = 1 and |w| ≤ n}¯.
In terms of Cayley graphs, `n is the number of geodesic loops in X(G, A) withthe base point 1 and length ≤ n. It is also described in the following way. Let
F be the free group with the free basis A. Let H be the kernel of the canonicalhomomorphism of F onto G. Then X(G, A) is identified with the quotient graph
H\X(F, A). Since X(F, A) is a regular tree, and is the universal covering graph¯over X(G, A), applying¯ the unique lifting property of covering maps, we have `n =¯{h ∈ H; d(1, h) ≤ n}¯, where d is the distance function on X(F, H).
The cogrowth rate is defined to be ` = lim `1/n
n . Grigorchuk showed that thisn→∞limit exists, and(i) 1 ≤ ` ≤ q;(ii) ` = 1 if and only if G is the free group with the basis A;
32See also J. M. Cohen [30].

33Our definiton of Cayley graphs is slightly different from the conventional one (cf. [110]).

DISCRETE GEOMETRIC ANALYSIS

17(iii) ` = q if and only if G is amenable;(iv) if G is not a free group, then q 1/2 < ` ≤ q.
The cogrowth sequence is directly related to the adjacency operator A on the
Cayley graph X(G, A) by the formula
µ
¶
∞
X
1+z
n
(7.1)
`n z = trG.
1 − Az + qz 2
n=0Note that trG T = hT δ1 , δ1 i. The identity (7.1) is a consequence of (2.2). Indeed, if
we put¯¯
mn = ¯{w; w is a reduced word over A with g(w) = 1 and |w| = n}¯¯¯= ¯{h ∈ H; d(1, h) = n}¯,then (2.2) and the identity mn = trG An lead toµ¶∞X
1 − z2mn z n = trG.
1 − Az + qz 2
n=0
Since

∞
X
n=0

mn z n = (1 − z)∞X`n z n , we get (7.1).

n=0

In the case where G is of infinite order, we have, for α = sup σ(A)(i) 2q 1/2 ≤ α ≤ q + 1;(ii) α = 2q 1/2 if and only if G is a free group with the basis A;(iii) α =¡q + 1 if and only ¢if G is amenable;(iv) ` = α + (α2 − 4q)1/2 /2 provided that G is not free.
The cogrowth rate is a complementary concept of the growth rate which ismore classical in theory of¯discrete groups. In group-theoretic terms, it is defined as¯
b = lim b1/n
where bn = ¯{g ∈ G; there exists a word w with g = g(w), |w| ≤ n}¯.
nn→∞The growth rate enjoys similar statements as the cogrowth rate.
(i) 1 ≤ b ≤ q;(ii) if b = 1, then G is amenable;(iii) if G is the free group with the basis A, then b = q.
The relation between b and the spectrum is less exact. The following is a special
case of inequality (5.3) (assume |G| = ∞).
sup σ(A) ≥2(q + 1)
b1/2 + b−1/2.

The spectrum of A seems to have a band structure for a broad class of finitely
generated groups G. A sufficient condition is given in terms of group C ∗ -algebras.
Let C ∗ (G) be the C ∗ -algebra which is defined as the norm-completion of the algebraof equivariant bounded operators T on `2 (V ) such that T δx has finite support forevery x ∈ G (the algebra C ∗ (G) is what we call the reduced C ∗ -group algebra of G).
Obviously A ∈ C ∗ (G). Suppose that there exists a positive constant c such that
trG P ≥ c for every non-zero projection P ∈ C ∗ (G). Then E(a) − E(b) ∈ C ∗ (G)for a > b with a, b 6∈ σ(A), where {E(λ)} is the spectral resolution for A. Hence
σ(A) is a finite union of closed intervals. Free groups and surface groups are such
examples satisfying this condition.
On the other hand, there is a class of Schreier graphs such that the spectraof the adjacency operators have peculiar structures; for instance, it may happen

18

TOSHIKAZU SUNADA

that the spectrum is the union of a set of isolated points S and a Cantor set C
where C consists of accumulation points of S and is obtained as the Julia set ofa certain polynomial. Examples belonging to such a class arise from the Hanoi
Towers Game which is described in terms of a rooted tree and its automorphismgroup. See [50] for the detail34. The reference [49] provides many examples withinteresting spectral properties.
Let us mention a useful formula which was skillfully applied to the constructionof Ramanujan graphs in [90]. Suppose that G is a finite group with a finite set ofgenerators A, and take the free group F and its subgroup H as before. If we put
[n/2]

tn =

X

[n/2]

mn−2k =k=0X¯¯¯{h ∈ H; d(1, h) = n − 2k}¯,k=0

then, in veiw of (2.3), we find∞X

tn z n = trG

n=0

N −1
1
1
1
1
1 X
=
tr
=
,
1 − Az + qz 2
|G| 1 − Az + qz 2
N i=0 1 − µi z + qz 2

where N = |G| and q + 1 = µ0 > µ1 ≥ · · · ≥ µN −1 ≥ −(q + 1) are eigenvaluesof A. Recall that the Chebychev polynomial Un of the second kind is defined by
Un (cos θ) = sin(n + 1)θ/ sin θ and satisfies
∞
X
1
(7.2)
Un (µ)z n =.
1 − 2µz + z 2
n=0
Obviously U2n−1 (−µ) = −U2n−1 (µ), U2n (−µ) = U2n (µ), and

1
−n−1

− α−n−1 ) (µ2 6= 1) α−β (βUn (µ) = n + 1(µ = 1) ,n(−1) (n + 1)(µ = −1)
where α, β are the solutions of z 2 − 2µz + 1 = 0. Comparing (7.2) with (2.3) above,
we have35
N −1
³ µ ´
q n/2 X
i
(7.3)
tn =
Un √ .
N i=0
2 q
We also find


´
³
P
n+1
q+1
n/2

√
= q q−1−1 = d|qn d,
q
U

n
2
q


³
´
P
n+1
√
(7.4)
q n/2 Un −(q+1)= (−1)n q q−1−1 = (−1)n d|qn d,
2
q

³
´

 n/2

q Un 2µ√iq = o(q n ) (|µi | < q + 1).
P
When H = F , we have tn = d|qn d, and 8tn coincides with the number of representations of q n as a sum of 4 squares provided that q is an odd prime (Jacobi).
This observation gives rise to anticipation that a number theoretic meaning may
be given to tn for a class of normal sungroups H.
In [90], starting from the ring of integral quaternions H(Z), Lubotzky, Phillips
and Sarnak constructed a finite Cayley graph X(G, A) = H\X(F, A), with G =34The group studied in [50] has many interesting properties. For instance, it is amenable
and not elementary (see [134]).
35This formula can also be derived from the pre-trace formula (see [90]).

DISCRETE GEOMETRIC ANALYSIS

19

P GL2 (Z/pZ) or P SL2 (Z/pZ), of degree q + 1 such that 2tn is expressed as thenumber of representatives of q n by the quadratic form x1 2 + (2p)2 x2 2 + (2p)2 x3 2 +(2p)2 x4 2 , where p, q are unequal primes both ≡ 1 (mod 4). Thus 2tn is the Fourier
coefficient of a modular form of weight two for the congruence subgroup Γ(16p2 ),and hence expressed as the sum of the Fourier coefficient a(q n ) of a cusp form
and the coefficient δ(q n ) of an Eisenstein series. The Ramanujan conjecture (nowa theorem) says a(q n ) = O² (q n(1/2+²)) for an arbitrary positive ². On the otherP
hand, δ is of the form δ(m) = d|m dS(d) with a periodic function S on N. It isP
easily verified that, if d|qn dR(d) = o(q n ) for a periodic function R on N, thenPd|q n dR(d) = 0. Using this fact, (7.4), and the Ramanujan bound, we find that,in the equality (7.3) (twice both sides, to be exact,
so that the left hand³´
³ side is
´
q+1
n
n
n
−1 n/2−1 n/2√√a(p ) + δ(p )), the terms δ(p ) and 2N q Un 2 q (and 2N q Un − 2q+1
q
if this appears) are cancelled out. We therefore get, as n → ∞,
N
−2
X

(7.5)

Un

³ µ ´
i
√ = O² (q n² ) (bipartite case),
2 q

Un

³ µ ´
i
√ = O² (q n² ) (nonbipartite case).
2 q

i=1
N
−1
X

(7.6)

i=1

√
√
This implies that |µi | ≤ 2 q for 1 ≤ i ≤ N −1 in non-bipartite case, and |µi | ≤ 2 q
for 1 ≤ i ≤ N − 2 in bipartite case. For, noting that |α| = |β| = 1 if |µ| ≤ 1, we
find that, on the left hand sides of (7.5) and (7.6), the terms corresponding to µi√
with |µi | > 2 q grow faster than q n² if we take ² small enough, while the terms√
corresponding to µi with |µi | ≤ 2 q are bounded or has the bound n + 1. Hencetaking a¡ look at (7.5)
and (7.6) for even n (to avoid cancellations), we get the claim.
¢√
Thus Λ X(G, A) ≤ 2 q, and the graph X(G, A) is Ramanujan.
8. Ihara zeta functions
Zeta functions are the most favorite things for many mathematicians since
Q thefamous Riemann Hypothesis (RH) for the classical zeta function ζ(s) = p (1 −p−s )−1 still remains to be solved as a challenging problem in the 21st century,
whereas zeta functions some of which satisfy analogues of RH have been innovatedin various fields. A typical zeta function satisfying the RH is the Weil zeta function associated with a projective algebraic variety defined over a finite field. A
remarkable fact is that the Ramanujan conjecture for modular forms of even integral weight is reduced to the RH for the Weil zeta. Another classic zeta function
satisfying the RH (nearly, to be exact) is the Selberg zeta function associated witha cocompact torsion-free discrete subgroup of P SL2 (R), which may be expressedas an Euler product over prime closed geodesics in a Riemann surface of constantnegative curvature.
In 1966, Y. Ihara [70] introduced an analogue of the Selberg zeta function
for a cocompact torsion-free discrete subgroup of P SL2 (Qp ), and proved its rationality by establishing a determinant formula. In the background, there is aconsensus that the p-adic version of the real hyperbolic plane GL2 (R)/(R× × O(2))
36
is GL2 (Qp )/(Q×p × GL2 (Zp )) . The latter space is, as a special case of Bruhat-Tits
36GL (Z ) and O(2) are maximal compact subgroups of GL (Q ) and GL (R), respectively.
2

p

2

p

2

20

TOSHIKAZU SUNADA

buildings, regarded as the set of vertices in the regular tree of degree p+1, and hence
its compact quotient yields a finite regular graph. To explain this briefly, we use
the fact that every element g ∈ GL2 (Qp )µcan be written¶ as the product g = k1 ak2 ,pm 0
where ki ∈ GL2 (Zp ) (i = 1, 2) and a =. The unordered pair {m, n}
0 pn
of integers depends only on g. Putting d(g) = |m − n|, and d(g1 , g2 ) = d(g1−1 g2 ), we
obtain the pseudo-distance d on GL2 (Qp ) satisfying d(gg1 , gg2 ) = d(g1 , g2 ). Sinced(g1 , g2 ) = 0 if and only if g1−1 g2 ∈ Q×
p · GL2 (Zp ), we get a GL2 (Qp )-invariant dis37
tance d on GL2 (Qp )/(Q×p × GL2 (Zp )) with nonnegative integral values . Defining×
the graph structure on GL2 (Qp )/(Qp × GL2 (Zp )) in such a way that x and y are
adjacent if and only if d(x, y) = 1, we obtain the regular tree of degree p + 1.
Thus it is natural to interprete the Ihara zeta functions in terms of finite regulargraphs. Let P be the set of all prime cycles in a finite regular graph X of degree
q + 1. Here a prime cycle is an equivalence class of a closed geodesic which is not apower of another one. Two closed paths are said to be equivalent if one is obtainedby a cyclic permutation of edges in another. In 1985, Sunada [122], following
the suggestion stated in the preface of J.-P. Serre [110], expressed the Ihara zetafunction as the Euler productY
Z(u) =(1 − u|p| )−1 ,p∈P

and gave a graph theoretic proof for a determinant expression in terms of the adjacency operator. Sunada’s observation was immediately generalized by K. Hashimotoand A. Hori [59] to the case of semi-regular graphs which correspond to p-adic semisimple group of rank one. It was H. Bass [11] who first noticed that “regularity”
of graphs is not necessary for a determinant expression. More precisely, what heestablished for a general finite graph X is the equality
¡
¢−1
(8.1)
Z(u) = (1 − u2 )χ(X) det I − uA + u2 (D − I),
where χ(X) denotes the Euler number of X. Moreover, if X is a non-circuit
graph, then u = 1 is a pole of Z(u) of order b1 = dim H1 (X, R), and limu→1 (1 −u)−b1 Z(u)−1 = 2b1 χ(X)κ(X). In the case of a regular graph of degree q + 1, (8.1)¡¢−1
reduces to the identity Z(u) = (1 − u2 )(1−q)N/2 det I − uA + qu2 I, from which
it follows that the Ihara zeta function of a regular graph X satisfies the RH if andonly if X is Ramanujan38.
There have been many work on the Ihara zeta function including new proofsof (8.1) and various generalizations (L. Bartholdi [10], H. Mizuno and I. Sato [94],[95], C. K. Storm [117], I. Sato [106]). An instructive proof together with ageneralization to weighted graphs is seen in M. D. Horton, H. M. Stark and A. A.
Terras [67]. See also [83] in which the idea of discrete geodesic flows is employed.
Actually, the Ihara zeta function is interpreted as the dynamical zeta function
associated with a symbolic dynamical system.
37It is interesting to compare this distance function with the Poincaré metric on GL R)/(R× ×2«
a 0
O(n)) induced from d(g) = | log
k2 with k1 , k2 ∈ O(2).
1
0 b38The RH for the Ihara zeta means that every pole s of ζ(s) = Z(q −s ) in the region 0 <Re s < 1 lies on the line Re s = 1/2.

„

ab−1 |, where g = k

DISCRETE GEOMETRIC ANALYSIS

21

One may make a “miniature” of algebraic number theory in the graph setting
which provides Ihara zeta functions with “moral support”. Indeed, prime cycles
behave like prime ideals in number fields under a finite-fold covering map. Hencethe number theoretic notions such as ideal groups, Frobenius substitutions andideal class groups have matching parts in graphs39. We may even formulate theclass field theory40 in the discrete setting. Note that the “ideal class group” of X is
nothing but H1 (X, Z). A big difference from number theory is that the ideal classgroup is of infinite order.
As a matter of course, we may imitate analytic number theory. For simplicity,
we treat regular graphs of degree q + 1 (for general graphs, a dynamical viewpoint¯is more convenient
to handle this matter). The counting function π(n) = ¯{p ∈¯P ; |p| = n}¯ has the following asymptotic behavior
qn(1) when X is non-bipartite; π(n) ∼(n → ∞).
nnq(2) when X is bipartite, π(n) ∼ 2(n = even → ∞).
n
41
These asymptotics , whose proof is almost trivial, are regarded as a discrete analogue of the prime number theorem. This observation brings us to the question“what is an analogue of the density theorem for primes in an arithmetic progression (and its generalization to number fields; that is, the Chebotarev density theorem) ?”. The¯ answer is an asymptotic¯ formula, if any, for the counting function
π(n, [g]) = ¯{p; |p| = n, ϕ(p) ∈ [g]}¯, where ϕ is a surjective homomorphism of
the fundamental group π1 (X) onto a finite group G. A tool is graph theoretic
L-functions. The L-function associated with
Q a finite dimensional unitary representation ρ of π1 (X) is defined as Lρ (u) = p∈P det(I − ρ(p)u|p| )−1 . It possesses a
determinant formula involving the twisted adjacency operator Aρ . Mimicking theproof in number theory, we may establish a density theorem in this set-up ((see[67] for a generalization to weighted graphs))42. Much difficult is the case when
G is of infinite order. So far abelian cases have been studied intensively. In thespecial case G = H1 (X, Z), it is verified (cf. [77] and [78]) that, for α ∈ H1 (X, Z),³ N (q − 1) ´b1 /2 q n(1) (non-bipartite case) π(n, α) ∼ κ(X)1/2(n → ∞);
nnb1 /2+1³ N (q −4π
´
b
/2
1) 1
q
(2) (bipartite case) π(n, α) ∼ 2κ(X)1/2(n = even →4π
nb1 /2+1∞).
The zeta function for an infinite-fold covering graph over a finite regular graph
was introduced by Grigorchuk and Zuk [49] as a suitable limit of Ihara zeta functions. In their discussion, the idea of densities of states is employed. They carried out explicit computation for a class of Schreier graphs associated with fractalgroups. B. Clair and S. Mokhtari-Sharghi [29] handled the zeta function for an
infinite graph with a group action which is defined as an Euler product over grouporbits of prime cycles. As is expected, the notion of von Neumann trace comes up
39

In the Riemannian geometric setting, a similar formulation has already been carried out in[121], [120]. See [67] and K. Hashimoto [60] for the case of graphs.
40
This corresponds to the class field theory for unramified extensions, to be exact.
41Actually we have an exact formula for π(n). We may obtain a similar asymptotic for ageneral graph.
42The idea for closed geodesics in manifolds is already seen in [119].

22

TOSHIKAZU SUNADA

in their determinant expressions. See D. Guido, T. Isola, and M. L. Lapidus [58],[57] for the recent development in this direction. The zeta function for a regularcovering graph is related to the counting function π(n, [1]). In this connection,
it is interesting to establish the Chebotarev type theorem for non-abelian “Galois
group” of infinite order.
A lucid meaning is given for the zeta functions of Cayley graphs as follows. A
word w = (b1 , . . . , bn ) is said to be cyclically reduced if bi+1 6= bi (i = 1, 2, . . . , n − 1)and b1 6= bn . A cyclically reduced word w is said to be prime if it is not a power ofanother word. Two words w1 and w2 are equivalent if w1 is obtained from w2 bya cyclic permutation. Letting now P be the set of equivalence classes of cyclicallyreduced prime words w with g(w) = 1, we define the zeta function Z(u) in the same
way as the Ihara zeta function. We then have, in a small neighborhood of u = 0,
Z(u) = (1 − u2 )−(q−1)/2 detG (1 − Au + qu2 )−1 ,where detG stands for the G-determinant defined by detG (T ) = exp trG (log T )43.
We conclude this section with more about analogy between hyperbolic spaces
and regular trees.

Figure 2(1) As was carried out by P. Cartier [22], harmonic analysis on regular trees
can be developed in a parallel way as that on hyperbolic spaces (see also A. FigaTalamanca and C. Nebbia [45]). Indeed, the ideal boundary and horospheres aredefined in a natural manner with which we may introduce the notion of sphericalfunctions and the Fourier transformation. This allows us to perform the detailed
spectral decomposition of the adjacency operator. For the reader’s convenience, weshall give a brief account. Fix a vertex o in X, and put S(n) = {x ∈ V ; d(x, o) = n}.
For each x ∈ S(n), there is a unique y ∈ S(n − 1) such that d(x, y) = 1, so that one
can define a map πn : S(n) −→ S(n − 1) by setting πn (x) = y. The boundary of X,
43This unpublished work was presented by the author at the memorial symposium for HubertPesce in 1998 at Grenoble. The definition of detG here is rather formal and is justified by afunctional-analytic argument. This determinat formula does not imply that the function Z(u) is
analytically continued to the whole complex plane C.

DISCRETE GEOMETRIC ANALYSIS

23

which we denote by ∂X, is defined as the projective limit lim(S(n), πn ). By Kol←−

mogoroff’s
exists a (unique) probability measure µ on ∂X satisfying¡ −1 ¢theorem, thereen (x) = |S(n)|−1 = (q + 1)−1 q 1−n for x ∈ S(n), where ω
en : ∂X −→ S(n) isµ ω
the projection map. Let b = (o, x1 , x2 , . . .) ∈ ∂X, and define the horosphere Hn (b)through b and xn by H`n (b) = {x ∈ V ; d(x, xk ) = k − n for sufficiently large k}.
It is evident that V = n Hn (b). Define a function
hx; bi on X × ∂X by putting√hx; bi = n when x ∈ Hn (b). We set λθ = q 1/2 e −1θ , and define the Fourier transforP
hx;bimation of a function f ∈ C(V ) with finite support by (Ff )(θ, b) = x∈V f (x)λ−θ .
¡¢−1
We also define a(θ) = 2q(q+1) sin2 θ (q+1)2 −4q cos2 θ. Then the map f 7−→ Ff
extends to a unitary isomorphism
F : `2 (V ) −→ L2 ([0, π] × ∂X,

1a(θ)dθdµ(b)),π

and the following inversion formula holds
Z Z
1 πhx;bi ˆf (x) =λf (θ, b)a(θ)dµ(b)dθ.
π 0 ∂X θ
Furthermore we find that FAF−1 coincides with the multiplication operator by the√function 2 q cos θ.
(2) Quite a bit related to harmonic analysis is the Selberg trace formula, an
indispensable tool to treat the Selberg zeta function. This also has a counterpart
in regular trees (G. Ahumada [2]). Let h(θ) be a real analytic function on R
satisfying (i) h(θ + 2π) = h(θ); (ii) h(−θ) = h(θ); (iii) h(θ) is analytically continued
to |Im θ| < 12 log q + ² (² > 0). Then, for a finite regular graph X0 of degree q + 1,
we have
Z π
N
−1
∞
X
XX
2N
sin2 θ
h(θi ) =q(q + 1)h(θ)
dθ+|p|q −n|p|/2 bh(n|p|).
2 − 4q cos2 θ
π
(q
+
1)
0
n=1
i=0
p∈P

Here µi = 2q 1/2 cos θi is an eigenvalue of A and
Z 2π
√
1
b
h(k) =
h(θ)e −1kθ dθ.
2π 0
The trace formulae with some special test functions h have been applied to thestudy of Ramanujan graphs by many people (cf. [18], [105], [133], [130]). See also
U. Smilansky [115] for trace formulae derived from a physical viewpoint.
In the proof of Ahumada’s formula, the pre-trace formula (6.3) is employed for
G = π1 (X0 ). In a sense, the determinant formula for the Ihara zeta function isconsidered a “product” version of the trace formula.
(3) One may apply the trace formulae to study the statistics of eigenvalues. Let{Xn }∞
graphs of degree q+1 such that lim
n=1 be a family of regular¯¯ n→∞ girth(Xn ) =∞44. Denote φn ([a, b]) = ¯{eigenvalues µ of AXn with µ ∈ [a, b]}¯. Then we haveZ b
1
φn ([a, b]) =φ(µ) dµ,(8.2)
limn→∞ |Vn |a
44The girth is the number of edges in the shortest closed geodesic.

24

TOSHIKAZU SUNADA

where
(8.3)


p

4q − µ2
q + 1φ(µ) =
2π (q + 1)2 − µ20(|µ| ≤ 2q 1/2 ).

(otherwise)This is an analogue of the result due to H. Huber [68] for eigenvalues of the Laplacians on hyperbolic surfaces.
We may also establish the semi-circle law45. Suppose a family ofp regular
graphs {Xn }∞satisfies
girth(X
)
→
∞,
deg
X
=
q
+
1
→
∞
and
deg Xnnnnn=1¯
×(log girth(Xn ))−1 → 0. Let ψn ([a, b]) = ¯{eigenvalues µ of AXn such that µ ∈
¯
√
1/2
1/2
[2qn a, 2qn b]}¯. Define ψ(x) = 2 1 − x2 /π (|x| ≤ 1), ψ(x) = 0 otherwise. Then
Z b
1
(8.4)
lim
ψn ([a, b]) =ψ(x) dx.
n→∞ |Vn |a
The function (8.3) is nothing but the density of states for A. Actually (8.2) isa special case of (6.2) if {Xn } is a tower of covering graphs.
(4) We may classify irreducible unitary representations of the automorphismgroup of a regular tree. This was put into practice by Ol’shanski [101],[102], andresembles the classification for SL2 (R). See also [45]. Closely related is unitary
representations of G = P GL2 (Qp ) which is a subgroup of the automorphism groupof the regular tree of degree p + 1. A sample of results in this theory asserts that,for a cocompact lattice Γ in G, no representation from the complementary seriesoccurs in L2 (Γ\G) if and only if the graph Γ\G/P GL2 (Zp ) is Ramanujan (cf. [91]).
9. Random walks
Another important source of discrete geometric analysis is the theory of random
walks, a synonym in a loose sense for a time homogeneous Markov chain on a countable state space. In terms of a graph X = (V, E), a random walk46 is a stochastic
process associatedP with a function p on E (called a transition probability) satisfyingp(e) ≥ 0 and e∈Ex p(e) = 1. The transition operator P : C(V ) −→ C(V ) is de¡¢Pprobability p(n, x, y) is
fined by P f (x) = e∈Ex p(e)f t(e) . The n-step transition P
defined to be the kernel function of P n ; namely (P n f )(x) = y∈V p(n, x, y)f (y). If
we put fn = P n f , then fn+1 − fn = (P − I)fn , f0 = f . Thus {fn } satisfies an analogue of the heat equation ∂f /∂t = −∆f if we think of I−P as an analogue of Laplacians. In general, however, it is not a discrete Laplacian in our sense. It is the case47
only if the random walk is symmetric, namely¡¢¡¢there exists a positive-valued function m on V such that p(e)m o(e) = p(e)m t(e) . Indeed, this being the case,¡ I−P¢
is the discrete Laplacian for the weight functions mV = m, mE (e) = p(e)m o(e) .
Note that p(n, x, y)m(y)−1 (= p(n, y, x)m(x)−1 ) is the kernel function of P n withrespect to the measure m. The most canonical one is the simple random walk withthe transition probability defined by p(e) = 1/deg o(e). In this case, I −P coincides
with the canonical Laplacian I − D−1 A. In what follows, we only handle symmetricrandom walks.
45This was stated by the author in the Japanese magazine “Su-Semi” in 2001. See also [96].
46Strictly speaking, we consider the case of finite range random walks.
47The term “reversible” is also used.

DISCRETE GEOMETRIC ANALYSIS

25

A central theme for random walks is the properties of p(n, x, y) as n goes toinfinity (see [137] for an overview). One of the most classical problems is therecurrence-transienceproblem48 which is concerned with the divergence and conP∞
vergence of n=1 p(n, x, y). If the series diverges, then a walker tends to return
again and again to finite regions in probability one; whereas, if it converges, then
the walker goes to “infinity” in probability one. For instance, if the Cheeger constant is positive, then the random walk is transient. In the transient case, it isnatural to consider the “ideal boundaries” (e.g., the Martin boundary or the Poisson boundary) which consist of “points” at infinity reached by the random walker
when n goes to infinity. The ideal boundaries are related to the problem on the existence of positive or bounded harmonic functions and also to the Dirichlet problem
at infinity (see V. A. Kaimanovich and W. Woess [76]).
The central limit theorem, a generalization of the Laplace-de Moivre theorem,
has been studied in detail for random walks on crystal lattices with periodic transition probability. In F. Spitzer [116], a classical book on random walks on Cayley
graphs X(Zn , A), one can find various results including the central limit theorem.
For general crystal lattices, see A. Y. Guivarc’h [56] and A. Krámli and D. Szász[86]. The perturbed eigenvalues λ0 (χ) for the twisted Laplacian (see Section 6)
play an important role in the proof. Interesting is the fact that asymptotics forthe simple random walk on a crystal lattice involve a generalization of discrete Albanese maps ([80], [82]). In fact, p(n, x, y) for a d-dimensional crystal lattice has
the following asymptotic expansion49 at n = ∞.
¡
¢−1
£
¤
(9.1) p(n, x, y) deg y∼ (4πn)−d/2 C 1 + c1 (x, y)n−1 + c2 (x, y)n−2 + · · · ,where the coefficient c1 (x, y) is expressed as
C0 e2ekΦ(x) − Φ(y)k+ g(x) + g(y) + c
4e : X −→ Rd is whatwith a certain function g(x) and a constant c. The map Φ
we call the standard realization, which turns out to coincide with the lifting of thediscrete Albanese map when X is the maximal abelian covering graph over a finite
graph. In view of (9.1),(9.2), we haven p(n, x, x) p(n, y, y)o2ee
C 0 kΦ(x)− Φ(y)k= lim 2n+−2 ,n→∞p(n, y, x) p(n, x, y)(9.2)

c1 (x, y) = −e is a realization with maximal symmetry. This
from which we may deduce that Φ
is rephrased as “the random walker detects somehow the most natural way for his
crystal lattice to sit in space”.
The theory of large deviations exhibits another aspect of asymptotics. This
theory, in general, concerns the asymptotic behavior of remote tails of sequencesof probability distributions50. In our setting, the problem is to find an asymptotic
behavior of p(n, x, y) while y is kept near the boundary ∂Bn (x) = {y ∈ V ; d(x, y) =48Historically this question originates in Polya’s observation in 1921 of the simple random
walk on the hyper-cubic lattice Zk . What Polya showed is that the simple random walk on Z2 isrecurrent, while it is transient on Zk with k ≥ 3.
49For a technical reason, we suppose that X is non-bipartite. In the bipartite case, a slight
modification of the statement is required.
50We may trace back to Laplace and Cramér. It is Varadhan who introduced a unified formal
definition (1966).

26

TOSHIKAZU SUNADAn}. A satisfactory answer has been given for random walks on crystal lattices. Here
we describe a weak version restricted to the case of the maximal abelian coveringgraph X over a finite graph X0 . It tells that there exists a convex function H
on H1 (X0 , R) (possibly assuming +∞) such that, for ξ in the interior of DH , ande{yn }∞
n=1 in V such that {Φ(yn ) − nξ} is bounded, we have
lim

1

n→∞ n

log p(n, x, yn ) = −H(ξ),

where DH = {ξ; H(ξ) < ∞}. The convex function H is explicitly described interms of the maximal positiveµ0¡(ω) of
transition operators51¢ the twisted
P eigenvalues
ω(e)1Lω defined by Lω f (x) = e∈Ex p(e)ef t(e) (ω ∈ C (X0 , R)). More precisely,1
if we think of µ0 as a function on H (X0 , R) using the fact that Lω+df = e−f Lω ef(f ∈ C 0 (X0 , R)), then£¤H(ξ) =
sup(ξ, x) − log µ0 (x) .
x∈H 1 (X0 ,R)

The convex domain DH is identified with the scaling limit of “reachable” regions of
the random walker starting from x, and expressed as D°
H = {ξ ∈ H1°(X0 , R); kξk1 ≤P°P°1}, where the norm k · k1 on C1 (X0 , R) is defined by ° e∈E o ae e° = e∈E o |ae |1(E o ⊂ E is an orientation, i.e., E o ∩E o = ∅ and E o ∪E o = E). Thus DH is a convex
polyhedron. The metric space H1 (X0 , R) with the distance d∞ (ξ1 , ξ2 ) = kξ1 − ξ2 k1
turns out to coincide with the Gromov-Hausdorff limit of (X, n−1 d) as n goes toinfinity ([85] and M. Gromov [54]).
Another extreme is the case of trees. S. Sawyer and T. Steger [107] obtained
a central limit theorem for the radial part of random walks (possibly with infinite
range) on trees. See Y. Derriennic [39] and Y. Guivarc’h [55] for a related matters.
S. P. Lalley [88] established a local limit formula and a large deviation property for
random walks with finite range on free groups. The local limit formula says that
there are constants R > 1, C > 0 such that p(n, x, x) ∼ Cn−3/2 Rn .
Gaussian estimates for p(n, x, y) have been studied by many people. The business is to compare
p(n, x, y)¢ with a geometrically defined function of the form¡h(n, x, y) exp − g(x, y) n−γ (see [132]). Roughly speaking,the term¢ h(n, x, y)¡
corresponds to the volume growth of the graph, and exp − g(x, y) n−γ is related
to a certain isoperimetric inequality. A typical result due to A. Grigor’yan [51]and L. Saloff-Coste [104] says that, under the assumption that inf p(e) > 0, theestimates
h d(x, y)2 i
c1¢ exp −
p(n, x, y)m(y) ≤ ¡ √
(9.3)
,
c1 n
m B n (x)h d(x, y)2 i
c2¢ exp −
p(n, x, y)m(y) + p(n + 1, x, y) ≥ ¡ √c2 n
m B n (x)hold if and only if the following two conditions are satisfied:¡¢(1)¡ (Volume
doubling
condition)
There
existsapositive
C
such
that
m
B
(x)
2n
¢
≤ Cm Bn (x) for every n and x ∈ V .
51Actually, L is linearly equivalent to the twisted operator associated with a real characterωof H1 (X0 , Z).

DISCRETE GEOMETRIC ANALYSIS

27(2) (Poincaré inequality) There exists a positive constant C such that
X ¡
X
¢2
¡
¢
f (y) − f Bn (x) m(y) ≤ Cn2|df (e)|2 p(e)m o(e)y∈Bn (x)e∈Eo(e),t(e)∈Bn (x)

¡
¢
¡
¢−1 P
for all f ∈ C Bn (x) , where f Bn (x) = m Bn (x)y∈Bn (x) f (y)m(y).
If we restrict ourselves to Gaussian upper bound, then the Faber-Krahn type
inequality is involved. More precisely, under the volume doubling condition, (9.3)
is equivalent to the following inequality¡¢c ³ m Bn (x) ´αλ1 (A) ≥ 2(A ⊂ Bn (x))
n
m(A)
n
o
where α, c > 0 and λ1 (A) = inf kdf k2 /kf k2 ; f 6= 0, supp f ⊂ A .
We see interesting effects on p(n, x, y) when a graph has a fractal property.
Indeed, the “sub-gaussian” function
1 i
h ³ d(x, y)β ´ β−1c¡¢ exp −cnm Bnβ (x)turns up as a bound. For more details, see the papers [33], [49], [52] by A.
Grigor’yan, T. Coulhon, and A. Telcs.
At this point, it should not be surprising to be able to relate properties of random walks on the Cayley graph to the group structure, say group growth, amenability, hyperbolicity, etc. (see H. Kesten [79] as a pioneer work and [75] for recent
results).
10. Concluding remarks
The present article dwells only on discrete analogue of Laplacians. Needlessto say, there are a variety of related operators. For example, a discrete elastic
Laplacian appears in the microscopic study of crystals wherein the idea of twisted
operators proved to be very useful ([114]). This is actually a graph version of
the differential operator showing up in the elastic wave equation, and has been
implicitly introduced by physicists in the study of lattice vibrations52. We may
also consider a discrete Schrödinger operator with a magnetic field. In particular,
the notion of discrete Schrödinger operators with periodic magnetic fields on aGcovering graph X → X0 is formulated in a natural manner in terms of invariant
cohomology classes. Magnetic fields, which are closed 2-forms in the continuous
case, are identified with 2-cocycles in the group cohomology ([124], [84]). It is
worthwhile to note the following exact sequence in connection with the set-up.
¡
¢
¡
¢
¡
¢G
¡
¢
0 → H 1 G, U (1) → H 1 X0 , U (1) → H 1 X, U (1) → H 2 G, U (1) → 1.
Even in the case of periodic magnetic fields on a crystal lattice (more specificallyon Z2 ), non-commutative nature crops up in the study of spectra and causes very
curious phenomena ([71]). Related to this is the almost Mathieu operator whichacts in `2 (Z) by the formulaHα,θ,λ f (n) = f (n + 1) + f (n − 1) + 2λ cos(2παn + θ)f (n).
52It originated in the study of specific heat of crystalline solids by Einstein (1907) and Dybye(1912).

28

TOSHIKAZU SUNADA

In their recent article [6], A. Avila and S. Jitomirskaya solved the Ten Martini
Problem proposed by M. Kac and B. Simon53 claiming that the spectrum of thealmost Mathieu operator is a Cantor set for all irrational α and for all λ 6= 0 (seealso A. Shubin [113]).
My choice of topics is admittedly biased. For instance, I did not make reference
to the recent work of Green functions and random graphs. I also could not touchon the detail of self-similar graphs whose spectra display very interesting aspects.
I believe, however, that the exploration into the references below would help thereader in gathering materials for various subjects which I could not take up in thisarticle.
Acknowledgement. The author is grateful to Polly Wee Sy who has helped bycommenting upon the first draft, and also to Stephen Hyde, Michael O’Keeffe,Davide M. Proserpio, Peter Kroll, Edwin Clark, Johannes Roth, and Alan Mackay
for drawing his attention to relevant work in crystallography.
References[1] T. Adachi and T. Sunada, Density of states in spectral geometry, Comment. Math. Helvetici
68(1993), 480-493.
[2] G. Ahumada, Fonctions périodiques et formule des traces de Selberg sur les arbres, C. R.
Acad. Sci. Paris 305(1987), 709-712.
[3] N. Alon, Eigenvalues and expanders, Combinatorica, 6(1986), 83-96.
[4] N. Alon and V. D. Milman: λ1 , isoperimetric inequalities for graphs and superconcentrators,
J. of Comb. Th. B 38(1985), 78-88.
[5] M. F. Atiyah, Elliptic operators, discrete groups and von Neumann algebras, Asterisque 3233(1976), 43-72.
[6] A. Avila and S. Jitomirskaya, The ten martini problem, to appear in Ann. of Math.
[7] R. Bacher, P. De La Harpe, and T. Nagnibeda, The lattice of integral flows and the latticeof integral cuts on a finite graph, Bull. Soc. Math. France, 125(1997), 167-198.
[8] M. Baker and S. Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, preprint[9] R. Band, I. Oren, and U. Smilansky, Nodal domains on graphs - How to count them and why?, to appear in this volume.
[10] L. Bartholdi, Counting paths in graphs, Enseign. Math. 45(1999), 83-131.
[11] H. Bass, The Ihara-Selberg zeta function of a tree lattice, International. J. Math., 3(1992),
717-797.
[12] G. Berkolaiko, A lower bound for nodal count on discrete and metric graphs, mathph/0611026(2006).
[13] N. L. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc., 29(1997), 641682.
[14] N. L. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993.
[15] R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte, The dissection of rectangles
into squares, Duke Math. J., 7(1940), 312-340.
[16] R. Brooks, The fundamental group and the spectrum of Laplacian, Comment. Math. Helv.
56(1981), 585-598.
[17] R. Brooks, On the spectrum of noncompact manifolds with finite volume, Math. Z., 187(1984), 425-432.
[18] R. Brooks, The spectral geometry of k-regular graphs, J. d’Analyse 57(1991), 120-151.
[19] R. Brooks, Non-Sunada graphs, Ann. Inst. Fourier (Grenoble) 49(1999), 707-725.
[20] J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of SL2 (Fp ),preprint.
53The reason of the naming is the following. In 1981, Mark Kac, during his talk in a sessionof American Mathematical Society, offered ten Martinis to anybody who could solve the problem.
B. Simon who was then present at his talk formulated this problem in his review paper and called
it the Ten Martini Problem.

DISCRETE GEOMETRIC ANALYSIS

29[21] P. Buser, A note on the isoperimetric constants, Ann. Sci. École Norm. Sup., 15(1982), 213230.
[22] P. Cartier, Fonctions harmoniques sur un arbre, Symp. Math., 9(1972), 203-424.
[23] J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis,(R. C. Gunnning, ed.), Princeton Univ. Press (1970) 195-199.
[24] F. R. K. Chung, Spectral graph theory, Conf. Board Math. Sci. 92(1997).
[25] F. R. K. Chung, Diameters and Eigenvalues, J. of Amer. Math. Soc., 2(1989),187-196.
[26] F. R. K. Chung, Laplacians of graphs and Cheeger’s inequalities, Proc. Int. Conf. “Combinatorics, Paul Erdös is Eighty”, Keszthely (Hungary), (1993), 1-16.
[27] F. R. K. Chung and S. T. Yau, Eigenvalues of graphs and Sobolev inequalities, Combinatorics,
Probability and Computing, 4(1995), 11-26.
[28] F. R. K. Chung, V. Faber and T. A. Manteuffel, An upper bound on the diameter of a graphfrom eigenvalues associated with its Laplacian, SIAM. J. Discrete Math., 7(1994), 443-457.
[29] B. Clair and S. Mokhtari-Sharghi, Zeta functions of discrete groups acting on trees, J. Algebra237(2001), 591-620.
[30] J. M. Cohen, Cogrowth and amenability of discrete groups, J. of Funct. Analy. 48(1982), 301309.
[31] Y. Colin de Verdière, Spectres de graphes, Société Mathématique de France, Paris, 1998.
[32] L. Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg
21(1957), 63-77.
[33] T. Coulhon and A. Grigoryan, Random walks on graphs with regular volume growth, Geomand Functl Anal., 8(1998), 656-701.
[34] D. M. Cvetković, M. Doob, and H. Sachs, Spectra of Graphs, Academic Press, 1980.
[35] E. B. Davies, G. M. Gladwell, J. Leydold and P. F. Stadler, Discrete nodal domain theorems,
Lin. Alg. Appl., 336(2001), 51-60.
[36] M. Dehn, Zerlegung von rechtecke in rechtecken, Math. Ann., 57(1903) 314-332.
[37] O. Delgado-Friedrichs, M. O’Keeffe and O. M. Yaghin, Three-periodic nets and tilings: regularand quasiregular nets, Acta Cryst. A59(2003), 22-27.
[38] O. Delgado-Friedrichs, M. D. Foster, M. O’Keeffe, D. M. Proserpio, M. M. J. Treacy, O.
M. Yaghi, What do we know about three-periodic nets ?, Journal of Solid State Chemistry178(2005), 2533-2554.
[39] Y. Derriennic, Quelques applications du théorème ergodique sousadditif, Astérisque, 74(1980), 183-201.
[40] J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random
walks, Trans. Amer. Math. Soc., 284(1984), 787-794.
[41] J. Dodziuk and W. S. Kendall, Combinatorial Laplacians and isoperimetric inequality, In“From Local Time to Global Geometry, Control and Physiscs” ed. by K. D. Elworthy, Longman Scientific and Technical, 1986, 68-75.
[42] J. Dodziuk and L. Karp, Spectral and function theory for combinatorial Laplacians, Contemporary. Math., 73(1988), 25-40.
[43] H. Donnelly and P. Li, Pure point spectrum and negative curvature for noncompact manifolds,
Duke Math J., 46(1979), 497-503.
[44] V. G. Drinfeld, Finitely additive measures on S 2 and S 3 invariant with respect to rotations,
Func. Anal. Appl., 18(1984), p77.
[45] A. Figa-Talamanca and C. Nebbia, Harmonic Analysis and Representation Theory forGroups Acting on Homogeneous Trees, London Math. Soc. Lecture Note Series 162, Cambridge University Press, 1991.
[46] K. Fujiwara, The Laplacian on rapidly branching trees, Duke Math. J., 83(1996), 191-202.
[47] K. Fujiwara, Growth and the spectrum of the Laplacian of an infinite graph, Tohoku Math.
J., 48(1996), 293-302.
[48] R. I. Grigorchuk, Symmetric random walks on discrete groups, in “Multi-component Random
Systems”,132-152, Nauk, Moscow, 1971.
[49] R. I. Grigorchuk, A. Zuk, The Ihara zeta function of infinite graphs, the KNS spectral measureand integral maps, Random walks and geometry, 141-180, Walter de Gruyter GmbH and Co.
KG. 2004.
[50] R. I. Grigorchuk and Z. Sunić, Schreier spectrum of the Hanoi Towers group on three pegs,
to appear in this volume.

30

TOSHIKAZU SUNADA[51] A. Grigor’yan, The heat equation on non-compact Riemannian manifolds, (in Russian)Matem. Sbornik, 182(1991), 55-87. Engl. transl. Math. USSR Sb., 72(1992), 47-77.
[52] A. Grigor’yan and A. Telcs, Sub-Gaussian estimates of heat kernels on infinite graphs, Duke
Math. J., 109, 3(2001), 452-510.
[53] A. Grigor’yan and A. Telcs, Harnack inequalities and sub-Gaussian estimates for random
walks, Math. Ann., 324(2002), 521-556.
[54] M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhäuser,
1999.
[55] A. Y. Guivarc’h, Sur la loi des grand nombres et le rayon spectral d’une marche aléatoire,
Astérisque, 74(1980), 47-98.
[56] A. Y. Guivarc’h, Application d’un theoreme limit local a la transience et a la recurrence demarches de Markov, Colloque de Théorie du Potentiel –Jacques Deny–Orsay 1983, 301-332.
[57] D. Guido, T. Isola, and M. L. Lapidus, Bartholdi zeta functions for periodic simple graphs,
in this volume.
[58] D. Guido, T. Isola, and M. L. Lapidus, A trace on fractal graphs and the Ihara zeta function,
preprint.
[59] K. Hashimoto and A. Hori, Selberg-Ihara’s zeta functions for p-adic discrete groups, Advanced Studies in Pure Math., 15(1989), 171-210.
[60] K. Hashimoto, On the zeta- and L-functions of finite graphs, International. J. Math., 1(1990),
381-396.
[61] Yu. Higuchi, Random Walks and Isoperimetric Inequalities on Infinite Planar Graphs andTheir Duals, Dissertation, Univ. of Tokyo, January 1995.
[62] Yu. Higuchi and T. Shirai, The spectrum of magnetic Schrödinger operators on a graph withperiodic structure, preprint 1999.
[63] Yu. Higuchi and T. Shirai, Weak Bloch property for discrete magnetic Schrödinger operators,
preprint 1999.
[64] Yu. Higuchi and T. Shirai, Some spectral and geometric properties for infinite graphs, Contemporary Math. 347(2004), 29-56.
[65] Yu. Higuchi and Y. Nomura, Spectral structure of Laplacian on a covering graph, preprint.
[66] M. D. Horton, H. M. Stark, A. A. Terras, What are zeta functions of graphs and what are
they good for ?, Contemporary Math., 415(2006), 173-190.
[67] M. D. Horton, H. M. Stark, and, A. A. Terras, Zeta Functions of weighted graphs and coveringgraphs, to appear in this volume.
[68] H. Huber, Öber das Spektrum des Laplace-operators auf kompakten Riemannschen Flächen,
Comment. Math. Helv. 57(1982), 627-647.
[69] Y. Ihara, Discrete subgroups of P SL(2, kp ), Proc. Symp. Pure Math. AMS, 9(1968), 272-278.
[70] Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields,
J. Math. Soc. Japan, 18(1966), 219-235.
[71] D. R. Hofstadter, Energy levels and wave functions of Bloch electrons in a rational or irrational magnetic field, Phys. Rev. B 14(1976) 2239.
[72] S. T. Hyde and S. J. Ramsden, Polycontinuous mprphologies and interwoven helical net
works, Europhys. Lett., 50(2000), 135-141.
[73] S. Ishiwata, A central limit theorem on a covering graph with a transformation group ofpolynomial growth, J. Math. Soc. Japan, 55(2003), 837-853.
[74] J. Jostand and L. Todjihounde, Harmonic nets in metric spaces, preprint.
[75] V. A. Kaimanovich, The Poisson formula for groups with hyperbolic properties, Ann. of
Math., 152(2000), 659-692.
[76] V. A. Kaimanovich and W. Woess, The Dirichlet problems at infinity for random walks ongraphs with a strong isoperimetric inequality, Probab. Th. Rel. Fields 91(1992), 445-466.
[77] A. Katsuda and T. Sunada, Homology and closed geodesics in a compact Riemann surface,
Amer. J. Math., 110(1987), 145-156.
[78] A. Katsuda and T. Sunada, Closed orbits in homology clasees, Publ. Math. IHES., 71(1990),
5-32.
[79] H. Kesten, Symmetric random walks on groups, Trans. AMS, 92(1959), 336-354.
[80] M. Kotani and T. Sunada, Albanese maps and off diagonal long time asymptotics for theheat kernel, Comm. Math. Phys., 209(2000), 633-670.
[81] M. Kotani and T. Sunada, Jacobian tori associated with a finite graph and its abelian coveringgraphs, Advances in Apply. Math., 24(2000), 89-110.

DISCRETE GEOMETRIC ANALYSIS

31[82] M. Kotani and T. Sunada, Standard realizations of crystal lattices via harmonic maps, Trans.
AMS, 353(2000), 1-20.
[83] M. Kotani and T. Sunada, Zeta functions of finite graphs, J. Math. Sci. Univ. Tokyo, 7(2000),7-25.
[84] M. Kotani and T. Sunada, Spectral geometry of crystal lattices, Contemporary. Math., 338(2003), 271-305.
[85] M. Kotani and T. Sunada, Large deviation and the tangent cone at infinity of a crystal
lattice, Math. Z., 254 (2006), 837-870.
[86] A. Krámli and D. Szász, Random walks with internal degree of freedom, I. Local limit theorem,
Z. Wahrscheinlichkeittheorie 63(1983), 85-95.
[87] P. Kuchment and Y. Pinchover, Integral representations and Liouville theorems for solutionsof periodic elliptic equations, J. Funct. Analy., 181(2001), 402-446.
[88] S. P. Lalley, Finite range random walk on free groups and homogeneous trees, Ann. Probab.
21(1993), 2087-2130.
[89] V. Ya. Lin and Y. Pinchover, Manifold with Group Actions and Elliptic Operators, Memoirs
AMS, 540(1994).
[90] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan conjectures and explicit construction of
expanders, Proc. Symp. on Theo. of Comp. Sci. 86(1986), 240-246[91] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Birkhäuser, Basel,
1994.
[92] G. A. Margulis, Explicit constructions of concentrators, Probl. of Inform. Transm. 10(1975),
325-332.
[93] G. A. Margulis, Some remarks on invariant means, Monatsch. Math., 90(1980), 233-235.
[94] H. Mizuno and I. Sato, Bartholdi zeta functions of graph coverings, Journal of Combinatorial
Theory, Series B 89(2003), 27-41[95] H. Mizuno and I. Sato, Bartholdi zeta functions of digraphs, European Journal of Combinatorics 24(2003), 947-954[96] H. Mizuno and I. Sato, The semicircle law for semiregular bipartite graphs, J. Comb. Theory,
101(2003), 174-190.
[97] T. Nagano and B. Smith, Minimal varieties and harmonic maps in tori, Comm.Math.Helv.,
50(1975), 249-265.
[98] T. Nagnibeda, The Jacobian of a finite graph, Contemporary Math., 206(1997), 149-151.
[99] T. Nagnibeda and W. Woess, Random walks on trees with finitely many cone types, J. of
Theor. Prob. 15(2002), 383-422.
[100] Y. Ohno and H. Urakawa, On the first eigenvalue of the combinatorial Laplacian for agraph, Interdisciplinary Information Sciences 1(1994), 33-46.
[101] G. I. Ol’shianskii, Representations of groups of automorphisms of trees, Usp. Math. Nauk,303(1975), 169-170.
[102] G. I. Ol’shianskii, Classification of irreducible representations of groups of automorphismsof Bruhat-Tits trees, Functional Anal. Appl. 11(1977), 26-34.
[103] G. Quenell, Spectral diameter estimates for k-regular graphs, Adv. Math., 106(1994), 122148.
[104] L. Saloff-Coste, A note on Poincaré, Sobolev, and Harnack inequalities, Duke Math. J., 65
Internat. Math. Res. Notices, 2(1992), 27-38.
[105] P. Sarnak, Some Applications of Modular Forms, Cambridge University Press, New York,1990.
[106] I. Sato, Bartholdi Zeta Functions for Hypergraphs, The Electronic Journal of Combinatorics,
13(2006).
[107] S. Sawyer and T. Steger, The rate of escape for anisotropic random walks in a tree, Probab.
Theor. Related Fields, 76(1987), 207-230.
[108] G. E. Schröder, S.J. Ramsden, A. G. Christy and S.T. Hyde, Medial surfaces of hyperbolic
structures, Eur. Phys. J. B., 35(2003), 551-564.
[109] A. Selberg, Harmonic analysis and discontinuous subgroups in weakly symmetric Riemannian spaces with applications to Dirichlet series, J. Indian Math. Soc., 20(1956), 47-87.
[110] J. P. Serre, Trees, Springer-Verlag, 1980.
[111] T. Shirai, Asymptotic behavior of the transition probability of a simple random walk on aline graph, preprint.

32

TOSHIKAZU SUNADA[112] T. Shirai, The spectrum of infinite regular line graphs, Trans. Amer. Math. Soc., 352(2000),
115-132.
[113] M. Shubin, Discrete magnetic Laplacian, Commun. Math. Phys. 164(1994), 259-275.
[114] M. Shubin and T. Sunada, Mathematical theory of lattice vibrations and specific heat, Pureand Appl. Math. Quarterly, 2(2006), 745-777.
[115] U. Smilansky, Quantum chaos on discrete graphs, J. Phys. A: Math. Theor. 40(2007), 621630.
[116] F. Spitzer, Princiles of Random Walk, D. Van. Nostrand, 1964.
[117] C. K. Storm, The zeta function of a hypergraph, The Electronic Journal of Combinatorics,
13(2006).
[118] D. Sullivan, For n > 3 there is only one finitely additive rotationally invariant measure on
the n-sphere defined on all Lebesgue measurable subsets, Bull. Amer. Math. Soc., 4(1981),
121-123.
[119] T. Sunada, Trace formula, Wiener integrals, and asymptotics, in Proc. of the Franco-Japan
Seminar, Kyoto 1981, (1983), 103-113.
[120] T. Sunada, Geodesic flows and geodesic random walks, Adv. Stud. Pure Math., 3(1984), 4785.
[121] T. Sunada, Riemannian coverings and isospectral manifolds, Ann. Math., 121(1985), 169186.
[122] T. Sunada, L-functions in geometry and some applications, Springer Lecture Notes in Math.
1201, 1986, pp.266-284.
[123] T. Sunada, Fundamental groups and Laplacians, Proc. of Taniguchi Sympos., Geometry
and Analysis on Manifolds, 1987, Springer Lecture Notes in Math. 1339, 1986, pp.248-277.
[124] T. Sunada, A discrete analogue of periodic magnetic Schrödinger operators, Contemporary
Math., 173(1994), 283-299.
[125] T. Sunada, Unitary representations of fundamenatal groups and the spectrum of twisted
Laplacians, Topology 28(1989), 125-132.
[126] T. Sunada and M. Nishio, Trace formulae in spectral geometry, Proc. I.C.M. Kyoto 1990,
Springer-Verlag Tokyo 1991, 577-585.
[127] T. Sunada, Crystals that nature might miss creating, Notices of the AMS, 55(2008), 208-215.
[128] P. W. Sy and T. Sunada, Discrete Schrödinger operators on a graph, Nagoya Math. J. 125(1992), 141-150.
[129] A. Terras, Survey of spectra of Laplacians on finite symmetric spaces, Experiment Math.
5(1996), 15-32.
[130] A. Terras, A survey of discrete trace formulas, IMP Vol. Math. and Appl. 109(1999), 643681.
[131] A. Terras, Arithmetic Quantum Chaos, IAS/Park City Mathematical Series 12(2002), 333375[132] N. Th. Varopoulos, L. Saloff-Coste and T. Coulhon, Analysis and Geometry on Groups,
Cambridge University Press, 1992.
[133] A. B. Venkov and A. M. Nikitin, The Selberg trace formula, Ramanujan graphs and someproblems of mathematical physics, Petersburg Math. J. 5(1994), 419-484.
[134] S. Wagon, The Banach-Tarski Paradox, Cambridge University Press, 1985.
[135] A. F. Wells, Three Dimensional Nets and Polyhedra, Wiley (1977).
[136] W. Woess, Random walks on infinite graphs and groups - a survey on selected topics, Bull.
London Math. Soc. 26(1994), 1-60.
[137] W. Woess, Random Walks on Infinite Graphs and Groups, Cambridge Uni. Press, 2000.
[138] R. J. Zimmer, Ergodic Theory and Semisimple Groups, Birkhäuser, 1984[139] A. Zuk, Property (T) and Kazhdan constants for discrete groups, Geom. Funct. Anal., 13(2003), 643-670.
Department of Mathematics, Meiji University, Tama-ku, Kawasaki, Japan