J. Ramanujan Math. Soc. 18, No.1 (2003) 1–20

Ramanujan Graphs
M. Ram Murty
Department of Mathematics, Queen’s University, Kingston, Ontario, K7L 3N6,
Canadae-mail: murty@mast.queensu.ca
Communicated by: Dipendra Prasad
Received: January 8, 2003

In the last two decades, the theory of Ramanujan graphs has gained prominence primarily for two reasons. First, from a practical viewpoint, these graphs
resolve an extremal problem in communication network theory (see for example [2]). Second, from a more aesthetic viewpoint, they fuse diverse branchesof pure mathematics, namely, number theory, representation theory and algebraic geometry. The purpose of this survey is to unify some of the recent
developments and expose certain open problems in the area. This survey is by
no means an exhaustive one and demonstrates a highly number-theoretic bias.
For more comprehensive surveys, we refer the reader to [27], [9] or [13]. For a
more up-to-date survey highlighting the connection between graph theory andautomorphic representations, we refer the reader to Winnie Li’s recent survey
article [11].
A graph X is a triple consisting of a vertex set V = V (X), an edge set
E = E(X) and a map that associates to each edge two vertices (not necessarily
distinct) called its endpoints. A loop is an edge whose endpoints are equal.
Multiple edges are edges having the same pair of endpoints. A simple graph is
one having no loops or multiple edges. If a graph has loops or multiple edges,
we will call it a multigraph. When two vertices u and v are endpoints of anedge, we say they are adjacent and (sometimes) write u ∼ v to indicate this.
To any graph, we may associate the adjacency matrix A which is an n × nmatrix (where n = |V |) with rows and columns indexed by the elements ofthe vertex set and the (x, y)-th entry is the number of edges connecting x andy. Since our graphs are undirected, the matrix A is symmetric. Consequently,
all of its eigenvalues are real.
The convention regarding terminology is not clear in the literature. Most use
the term ‘graph’ to mean a simple graph as we have defined it above. Thus, the∗ Research partially supported by an NSERC grant.

1

2

M. Ram Murty

Ramanujan graphs constructed in the literature, which we shall refer to below,
have been all simple graphs. One can enlarge the definition of a Ramanujan
graph to the context of multigraphs so that their construction becomes slightly
simpler (see for instance, Theorem 8 below and the example that follows).
The degree of a vertex v, denoted deg(v), is the number of edges incident
with v, where we count a loop with multiplicity 2. With this convention, we
have the familiar “handshaking lemma” of graph theory:Xdeg(v) = 2|E(X)|.
v∈V

We will say an edge e has length 1, unless it is a loop, in which case we adopt
the convention that it has length 2. We will denote the length of e by `(e). For amultigraph, a walk of length r from x to y is a sequence x = v0 , v1 , ..., vr = ywith vi ∈ V and ei = (vi , vi+1 ) ∈ E for i = 0, 1, ..., r − 1 andX`(ei ) = r.
iA path is a walk with no repeated vertex. A word of caution must be inserted
here. In graph theory literature, the distinction between a walk and a path isas we have defined it above. However, in the number theory circles, the finer
distinction is not made and one uses the word ‘path’ to mean a ‘walk’. (See forexample, [20] and [26].) A graph is said to be connected if for any x, y ∈ V ,there is a path from x to y. The number of walks from x to y of length r
is clearly given by the x, y-th entry of Ar , where again we have adopted theconvention of counting a loop with multiplicity 2. A graph is called k-regular
if every vertex has degree k.
The following theorem is basic in graph theory.
Theorem 1. Let A be the adjacency matrix of an undirected graph X. Let
1(X) be the maximal degree of any vertex of X. If λ is an eigenvalue of A,
then |λ| ≤ 1(X).
Proof. Let v be an eigenvector of A corresponding to an eigenvalue λ. Then,
Av = λv. Write v = (x1 , ..., xn )t and assume without loss of generality that|x1 | = max1≤i≤n |xi |. Then,|λ||x1 | =

n
X
j =1

a1j xj ≤ |x1 |nX

a1j = |x1 |deg(v1 ) ≤ |x1 |1(X)j =1

from which we deduce |λ| ≤ 1(X). This completes the proof.

2

Corollary 2. If X is a k-regular graph, then all the eigenvalues λ of its
adjacency matrix satisfy |λ| ≤ k.

Ramanujan Graphs

3

Since a k-regular graph is one whose adjacency matrix has every row sum(and hence every column sum) equal to k, we clearly have that λ0 = k is aneigenvalue of A with eigenvector equal to u = (1, 1, ..., 1)t . The following
theorem makes this more precise.
Theorem 3. If X is a k-regular graph, then λ = k is an eigenvalue withmultiplicity equal to the number of connected components of X.
Proof. We have already proved the first part. Let v = (x1 , ..., xn )t be an eigenvector of A with eigenvalue k. Without loss of generality, suppose |x1 | =max1≤i≤n |xi |. We may also suppose x1 > 0. Then
kx1 =

n
X
j =1

a1j xj ≤nX

a1j x1 = kx1 .

j =1This means, that every j for which a1j 6= 0, we must have xj = x1 . In
particular, this is true for all j for which vj is adjacent to v1 . Repeating theargument with each of the neighbouring vertices, we deduce that xj = x1 if vj
is connected to v1 . As we may duplicate this argument for each component,
the result is now clear.
2
Thus, if X is a connected k-regular graph, we may arrange the eigenvalues as
k = λ0 (X) > λ1 (X) ≥ · · · ≥ λn−1 (X) ≥ −k.
It is not difficult to show that −k is an eigenvalue of X if and only if X
is bipartite, in which case its multiplicity is again equal to the number ofconnected components. Any eigenvalue λi 6= ±k is referred to as a nontrivial eigenvalue. We denote by λ(X) the maximum of the absolute values of
all the non-trivial eigenvalues. A Ramanujan multigraph is a k-regular graphsatisfying√
λ(X) ≤ 2 k − 1.
A Ramanujan graph is a Ramanujan multigraph having no multiple edges
or loops. The motivation for these definitions will become apparent in later
sections. The significance of such graphs will also be elaborated upon later.
For the moment, let us state that the explicit construction (see section 5 below)of such graphs for a fixed k and n → ∞ has only been described in the casek − 1 is prime [12], [14] or a prime power [15] and it is still an open problem
in the general case. Thus, the simplest case that is open is when k = 7. Thatis, we must construct a family of 7-regular graphs Xi with |Xi | tending to
infinity whose corresponding
adjacency matrices have non-trivial eigenvalues√
λ satisfying |λ| ≤ 2 6. In this context, Pizer [18] constructs what he calls

4

M. Ram Murty‘almost’ Ramanujan graphs by using the theory of Hecke operators. Moreprecisely, he shows that for every k, there is a family of k-regular graphs Xi with
|Xi | tending to infinity and the non-trivial eigenvalues √λ of the corresponding
adjacency matrices satisfy the inequality |λ| ≤ d(k −1) k − 1 where d(k −1)
denotes the number of positive divisors of k − 1.
The complete graph Kr as well as the bipartite graph Kr,r are easily seen to
be Ramanujan (see the discussion in section 2). The Petersen graph (see Figure1) is a 3-regular graph whose adjacency matrix has characteristic polynomial(λ − 3)(λ + 2)4 (λ − 1)5 , and thus is easily seen to be Ramanujan.
u
u

u

u

u

u

u

u

u

u

Figure 1. The Petersen GraphFriedman [5] has shown that random k-regular graphs are close to being
Ramanujan in the sense that λ1 (as defined above) satisfies√
λ1 ≤ 2 k − 1 + 2 log k + O(1).
1. Preliminaries
We can define a metric on a connected graph by defining the distance d(x, y)
for x, y ∈ V as the minimal length amongst all the paths from x to y. The
diameter of a connected graph is then the maximum value of the distancefunction. We begin by deriving a simple estimate for the diameter of a k-regulargraph involving λ(X) due to Chung [3]. If A is the adjacency matrix, then the(x, y)-th entry of Ar is the number of walks from x to y of length r. Hence, if
every entry of Am is strictly positive, then the diameter of X is at most m. We
will use this observation below to derive an upper bound for the diameter of ak-regular graph.

Ramanujan Graphs5

Let n = |V | and u0 , u1 , ..., un−1 be an orthonormal basis of eigenvectorsof A with corresponding eigenvalues λ0 , ..., λn−1 respectively. We may take√u0 = u/ n where u = (1, 1, ..., 1)t as defined earlier. We can write
A=

n−1
X

λi ui uti .

i=0More generally,
n−1
X

Ar =

i=0

λri ui uti .

In particular, we see that the (x, y)-th entry of Am isXtλm=i (ui ui )x,y .
i

If X is a connected k-regular graph, λ0 = k and the above expression is
≥

X
km
λm
−
i (ui )x (ui )y .
ni≥1

Let us assume that X is not bipartite (so that −k is not an eigenvalue). Then,by the Cauchy-Schwarz inequality,
X
i≥1

λm
i (ui )x (ui )ym≤ λ(X)

Xi≥1!1/2(ui )2x

X
i≥1

!1/2
(ui )2y.

Recalling that the ui ’s form an orthonormal basis, this is easily seen to be≤ λ(X)m (1 − (u0 )2x )1/2 (1 − (u0 )2y )1/2 ≤ λ(X)m (1 − 1/n).
Thus, the (x, y)-th entry of Am is always positive if
km> n − 1.
λ(X)mIn other words, we have proved
Theorem 4. (Chung, 1989) Let X be a k-regular graph with n vertices anddiameter m. If X is not bipartite, thenm≤log(n − 1)
+ 1.
log(k/λ(X))

6

M. Ram Murty

A similar result can be derived for k-regular bipartite graphs. In fact, by aminor modification of the above proof, one can show that for bipartite k-regulargraphs, we have (see [19])m≤log(n − 2)/2
+ 2.
log(k/λ(X))

The inequality of Theorem 4 shows that the diameter is minimized by minimizing λ(X). (Theorem 5 below also shows this.) In communication theory,
one requires the network to have small diameter for efficient operation.
There is another elementary observation about the eigenvalue λ(X) that is
worth making. Observe that the eigenvalues of AAt are simply the squares ofthe eigenvalues of A. On the other hand, the trace of AAt is simply kn for a
k-regular graph X. Thus, if X is not bipartite,
k 2 + (n − 1)λ(X)2 ≥ kn
which gives the inequalityλ(X) ≥

n−k
n−1

1/2

√

k.

If X is bipartite, then
2k 2 + (n − 2)λ(X)2 ≥ nk,
in which caseλ(X) ≥n − 2k
n−2

1/2

√

k.

If we think of k as fixed and n → ∞, then we see that√lim λ(X) ≥ k.
n→∞

A theorem due to Alon and Boppana (see [12]) asserts that√
lim inf λ(Xn,k ) ≥ 2 k − 1n→∞where the lim inf is taken over k regular graphs with n going to infinity. Several
proofs of this result exist in the literature [12], [9]. A sharper version wasderived by Nilli [17] (who is also known as N. Alon):
Theorem 5. (Nilli, 1991) Suppose that X is a k-regular graph. Assume thatthe diameter of X is ≥ 2b + 2 ≥ 4. Then√√
2 k−1−1
λ1 (X) ≥ 2 k − 1 −.
bRamanujan Graphs

7

To keep this paper self-contained, we give the proof in section 3 below.
Let us make the following observation. If m = d(u, v) is the diameter of X,
then the number of walks from u of length m is ≤ k m and as each such walk has
m + 1 vertices, we deduce that the number of vertices n satisfies the inequalityn ≤ (m + 1)k m .
Thus, if k is fixed and n → ∞, then the diameter also tends to infinity. In
particular, Theorem 5 implies the Alon-Boppana theorem since λ(X) ≥ λ1 (X).
2. Cayley graphs
There is a simple procedure for constructing k-regular graphs using grouptheory. This can be described as follows. Let G be a finite group and S a kelement multiset of G. That is, S has k elements where we allow repetitions.
We suppose that S is symmetric in the sense that s ∈ S implies s −1 ∈ S (withthe same multiplicity). Now construct the graph X(G, S) by having the vertex
set to be the elements of G with (x, y) an edge if and only if x −1 y ∈ S. Since
S is allowed to be a multiset, X(G, S) may have multiple edges.
If G is abelian, the eigenvalues of the Cayley graph are easily determined
as follows. The cognoscentii will recognize that it is the classical calculationof the Dedekind determinant in number theory.
Theorem 6. Let G be a finite abelian group and S a symmetric subset of G
of size k. Then the eigenvalues of the adjacency matrix of X(G, S) are given by
X
λχ =
χ(s)
s∈S

as χ ranges over all the irreducible characters of G.
Remark. Notice that for the trivial character, we have λ0 = k. If we have forall χ 6= 1
Xχ(s) < ks∈Sthen the graph is connected by our earlier remarks. Thus, to construct Ramanujan graphs, we requireX√χ(s) ≤ 2 k − 1s∈Sfor every non-trivial irreducible character χ of G. This is the strategy employedin many of the explicit constructions of Ramanujan graphs.

8

M. Ram Murty

Proof. For each irreducible character χ , let vχ denote the vector (χ(g) : g ∈G). Let δS (g) equal 0 if g ∈/ S, and m if g ∈ S with multiplicity m. Denote by
A the adjacency matrix of X(G, S). Thus, the i, j -th entry of A is the numberof edges between i and j . Then,
X(Avχ )x =δS (x −1 g)χ (g).
g∈G

By replacing x −1 g by s, we obtain(Avχ )x = χ(x)

X

!
χ (s)

s∈S

which shows that vχ is an eigenvector with eigenvalue
X
χ(s)
s∈S

2

which completes the proof.

We remark that in the above proof, we did not really use the symmetry of
the set S and so the result extends to Cayley digraphs as well.
As mentioned above, this calculation is reminiscent of the Dedekind determinant formula in number theory. Recall that this formula computes det A
where A is the matrix whose (i, j )-th entry is f (ij −1 ) for any function fdefined on the finite abelian group G of order n. The determinant is!
Y X
f (g)χ(g) .
χg∈GThe proof is analogous to the calculation in the proof of Theorem 6 and we leaveit to the reader. As an application, it allows us to compute the determinant of acirculant matrix. For instance, we can compute the characteristic polynomialof the complete graph. Indeed, it is not hard to see that by taking the additive
cyclic group of order n and setting f (0) = −λ, f (a) = 1 for a 6= 0, we obtainthat the characteristic polynomial is(λ − (n − 1))(λ + 1)n−1
by the Dedekind determinant formula. As the complete graph of order n is an(n − 1)-regular graph, we see immediately from the above calculation that it
is a Ramanujan graph.
Another example of a Ramanujan graph is the bipartite graph Kr,r . This isan r-regular graph whose adjacency matrix has eigenvalues equal to r, −r and
0 as is easily checked. In fact, its characteristic polynomial is(λ − r)(λ + r)λ2r−2 .

Ramanujan Graphs

9

If G is an abelian group and S is a subset of G, we can define another set ofgraphs Y (G, S) called sum graphs as follows. The vertices consist of elementsof G and (x, y) is an edge if xy ∈ S. If we allow S to be a multiset, then we
get a graph with multiple edges. Arguing as before, we can show (see [[9], p.
197]):
Theorem 7. Let G be an abelian group. For each character χ of G, theeigenvalues of Y (G, S) are given as follows. Define
X
eχ =
χ(s).
s∈S

If eχ = 0, then vχ and vχ −1 are both eigenvectors with eigenvalues zero. Ifeχ 6= 0, then|eχ |vχ ± eχ vχ −1
are two eigenvectors with eigenvalues ±|eχ |.
To begin, a simple example can be given using Gauss sums. For p an odd
prime, let G = Z/pZ and S be the multiset of squares. The multigraph X(G, S)
is easily seen to be Ramanujan in view of the fact (see for example, [[16], p.
81]):
X

e2πiax /p =2√px∈Z/pZ

for any a 6= 0. By our convention in the computation of degree of a vertex, we
see that X(G, S) is a p + 1-regular graph.
Using Theorem 7, Winnie Li [10] constructed Ramanujan graphs in thefollowing way. Let Fq denote the finite field of q elements. Let G = Fq 2 andtake for S the elements of G of norm 1. This is a symmetric subset of G and the
Cayley graph X(G, S) turns out to be Ramanujan. The latter is a consequenceof a theorem of Weil estimating Kloosterman sums (see [22]).
These results allow us to construct Ramanujan graphs by estimating character sums. However, by allowing S to be a multiset, the construction of Ramanujan multigraphs is slightly simplified, as the following theorem shows.
Theorem 8. Let G = Fq be a finite field of q = p m elements and f (x) apolynomial with coefficients in Fq and of degree 2 or 3. Let S be the multiset{f (x) : x ∈ Fq }.
Suppose S is symmetric. Then, Y (G, S) is a Ramanujan graph.

10

M. Ram Murty

The required character sum estimates come from Weil’s proof of the Riemann hypothesis for the zeta functions of curves over finite fields. In particular,
we have for all a ∈ Fq , a 6= 0,
X
x∈Fq

√
exp(2πitr Fq /Fp (af (x))/p) ≤ (degf − 1) q

provided f is not identically zero (see [[9], p. 94]). In particular, if f has√
degree 3, we get the estimate of 2 q for the exponential sum. For example, if
u ∈ Z/pZ and we takeS = {x 3 + ux : x ∈ Z/pZ},
then S is symmetric and, according to our convention, X(G, S) is a k-regulargraph with k = p + 1. In addition, it is a Ramanujan graph sinceX√
exp(2πia(x 3 + ux)/p) ≤ 2 p

x∈Z/pZby virtue of the Riemann hypothesis for curves (proved by Weil).
There is a generalization of these results to the non-abelian context. This isessentially contained in a paper by Diaconis and Shahshahani [4]. Using theirresults, one can easily generalize the Dedekind determinant formula as follows(and which does not seem to be widely known). Let G be a finite group andf a class function on G. Then the determinant of the matrix A whose rows
(and columns) are indexed by the elements of G and whose (i, j )-th entry isf (ij −1 ) is given by
!χ(1)
Y
1 X
f (g)χ(g)χ(1) g∈Gχwith the product over the distinct irreducible characters of G.
The following theorem is implicitly contained in [[4], p. 175].
Theorem 9. Let G be a finite group and S a symmetric subset which is stable
under conjugation. Let A be the adjacency matrix of the graph X(G, S) (whereu, v ∈ G are adjacent if and only if uv −1 ∈ S). Then the eigenvalues of A are
given by
λχ =

1 X
χ (s)
χ(1) s∈S

as χ ranges over all irreducible characters of G. Moroever, the multiplicity ofλχ is χ(1)2 .

Ramanujan Graphs

11

We remark that the λχ in the above theorem need not be all distinct. For
example, if there is a non-trivial character χ which is trivial on S, then themultiplicity of the eigenvalue |S| is at least 1 + χ (1)2 .
Proof. We essentially modify the proof on pp. 176–177 of [4] to suit ourcontext. We consider the group algebra C[G] with basis vectors eg with g ∈ G
and multiplication defined as usual by eg eh = egh . We define Q to be the linear
operator that acts on C[G] by left multiplication byXXes =δS (g)eg .
s∈S

g∈G

The matrix representation of Q with respect to the basis vectors eg with g ∈ G
is precisely the adjacency matrix of X(G, S) as is easily checked. If r denotes
the left regular representation of G on C[G], we find that the action ofXr(A) =r(s)s∈S

on C[G] is identical to Q. Moreover, C[G] decomposes as
C[G] = ⊕ρ Vρ
where the direct sum is over non-equivalent irreducible representations of
G and the subspace Vρ is a direct sum of degρ copies of the subspace Wρ
corresponding to the irreducible representation ρ. The result is now clear frombasic facts of linear algebra.
2
We refer the reader to [1] for a more detailed proof of the above in a slightly
general context.

3. Relating the diameter and λ1
In this section, we will give the promised proof of the following result of Nilli[17]:
Theorem 5.
then

Let X be a k-regular graph. If the diameter of X is ≥ 2b+2 ≥ 4,√√
2 k−1−1
λ1 (X) > 2 k − 1 −.
b

As we remarked earlier, the diameter goes to infinity as |X| goes to infinity.
Thus, we deduce:

12
Theorem 10.

M. Ram Murty(Alon-Boppana)√
lim inf λ(Xn,k ) ≥ 2 k − 1n→∞where Xn,k denotes a k-regular graph with n vertices.
We preface our proof of Theorem 2 with a few remarks from linear algebra.
Let A be a symmetric matrix (a similar analysis applies to Hermitian matrices).
Let λmax and λmin be the largest and smallest eigenvalues of A respectively.
Then, (see [[7], p. 176]) we have
(Av, v)(v, v)

λmax = max
v6=0

and
(Av, v).
v6=0 (v, v)

λmin = min

To see this, observe that if U denotes the matrix whose columns form an
orthonormal basis of eigenvectors of A, then we may write
A = U DU t
where D is a diagonal matrix whose diagonal entries are the eigenvalues of A.
Thus,
X(Av, v) = v t Av = v t U DU t v =λi |(U t v)i |2 .
i

As each of the terms |(U t v)i |2 is non-negative,
X
X|(U t v)i |2 ≤ v t Av ≤ λmax|(U t v)i |2 .
λmin
i

i

Since U is an orthogonal matrix, we have
X
X|(U t v)i |2 =|vi |2 = v t v.
Ii

Thus, if v 6= 0,λmin ≤(Av, v)≤ λmax .
(v, v)The inequalities are easily seen to be sharp by considering the eigenvectors
corresponding to λmax and λmin respectively, which proves our assertion. This
result is usually referred to as the Rayleigh-Ritz theorem in the literature.

Ramanujan Graphs

13

Now let L(X) denote the space of real-valued functions on X. We can equip
the vector space L(X) with an inner product by definingX(f, g) =f (x)g(x).
x∈X

We can view the adjacency matrix as acting on L(X) via the formulaXf (y).
(Af )(x) =(x,y)∈E

For a connected k-regular graph, λ0 = k is an eigenvalue of multiplicity 1 andthe corresponding eigenspace is the set of constant functions. Hence, we candecompose our space as
L(X) = Rf0 ⊕ L0 (X)where f0 ≡ 1 and L0 (X) is the space of functions orthogonal to f0 . Thus, we
can consider A as operating on L0 (X). By the Rayleigh-Ritz theorem,
λ1 (X) = max

f 6=0(f,f0 )=0

(Af, f ).
(f, f )

Since we want a lower bound for λ1 (X), it is natural to consider the matrix
1 = kI − A whose eigenvalues are easily seen to be k − λi (0 ≤ i ≤ n − 1).
(1 is a discrete analogue of the classical Laplace operator.) Thus,k − λ1 (X) = minf 6=0(f,f0 )=0

(1f, f ).
(f, f )The strategy now is to find a function f with (f, f0 ) = 0, that gives a goodupper bound on the quotient. We can now prove Theorem 5. We follow [9].
Proof of Theorem 5.
define sets

Let u, v ∈ G be such that d(u, v) ≥ 2b +2. For i ≥ 0,
Ui = {x ∈ G : d(x, u) = i}
Vi = {x ∈ G : d(x, v) = i}.

Then, the sets U0 , U1 , ..., Ub , V0 , V1 , ..., Vb are disjoint, for otherwise, by thetriangle inequality we get d(u, v) ≤ 2b which is a contradiction. Moreover,no vertex of
U = ∪bi=0 Ui
is adjacent to a vertex inV = ∪bi=0 Vi

14

M. Ram Murty

for otherwise d(u, v) ≤ 2b + 1 which is again a contradiction. For each vertex
in Ui , at least one lies in Ui−1 and at most q = k − 1 lie in Ui+1 (for i ≥ 1).
Thus,|Ui+1 | ≤ q|Ui |.
By the same logic, |Vi+1 | ≤ q|Vi |. By induction, we see that |Ub | ≤ q (b−i) |Ui |and |Vb | ≤ q (b−i) |Vi | for i ≥ 1. We will set f (x) = Fi for x ∈ Ui , f (x) = Gi
for x ∈ Vi and zero otherwise, with the Fi and Gi to be chosen later. Now,
(f, f ) = A1 + B1
where
A1 =

b
X
i=0

Fi2 |Ui |

and
B1 =

b
X
i=0

G2i |Vi |.

We now choose F0 = α, G0 = β, Fi = αq −(i−1)/2 and Gi = βq −(i−1)/2 fori ≥ 1. We choose α and β so that (f, f0 ) = 0.
Now we derive an upper bound for (1f, f ). Note that
1 X
(f (x) − f (y))2 = k(f, f ) − (Af, f ) = (1f, f )2 (x,y)∈E
by an easy calculation. Recall that no vertex of U is adjacent to a vertex of V .
Moreover, f is non-zero only on U ∪ V . Thus, if we let AU denote the sum
1 X(f (x) − f (y))22 (x,y)∈E
x or y ∈U

and let AV be defined similarly, then
(1f, f ) = AU + AV .
If we partition according to the contribution from each Ui and keep in mind
that each x ∈ Ui has at most q = k − 1 neighbours in Ui+1 , we obtain
AU ≤

b−1
X
i=1

|Ui |q q −(i−1)/2 − q −i/22

α 2 + |Ub |q · q −(b−1) α 2 .

Ramanujan Graphs

15

This is easily computed to be√= ( q − 1)2 |U1 | + |U2 |q −1 + · · · + |Ub−1 |q −(b−2) + |Ub |q −(b−1) α 2√+ α 2 (2 q − 1)|Ub |q −(b−1) .
Because q −(i−1) |Ui | ≥ q −i |Ui+1 |, for i ≥ 1, we have,
A1 − α 2√√AU ≤ ( q − 1)2 (A1 − α 2 ) + (2 q − 1)bwhich is less than

√
2 q −1
1+q −2 q +
A1 .
b
√

Similarly,√
2 q −1√
AV < 1 + q − 2 q +B1 .
bCombining these inequalities gives√
2 q −1AU + AV√k − λ1 (X) ≤<1+q −2 q +A1 + B 1bwhich proves the theorem, since k = q + 1.

2

The Alon-Boppana theorem can also be deduced from a result of Serre (asnoted in [[9], p. 209]). This says that for any  > 0, there exists a positive
constant c = c(, k) such that for every√ k-regular graph X, the number of
eigenvalues λ of X with λ > (2 − ) k − 1 is at least cn where n is thenumber of vertices of X. Thus, every√ k-regular graph has a positive proportionof eigenvalues larger than (2 − ) k − 1.
4. Expanders
For any subset A of a graph X, we may define the boundary of A, denoted ∂A,
by∂A = {y ∈ X : d(y, A) = 1}.
That is, the boundary of A consists of vertices which are adjacent to somevertex in A. Let c be a positive real number. A k-regular graph X with n vertices
is called a c-expander if
|∂A|
≥c
|A|

16

M. Ram Murty

for all subsets A with |A| ≤ |X|/2. Expander graphs play an important role incomputer science and the theory of communication networks (see [2]). Thesegraphs arise in questions about designing networks that connect many users
while using only a small number of switches. Our interest in them lies in thefact that the theory of c-expanders can be related to the eigenvalue questionsof the previous section.
The idea is to apply the Rayleigh-Ritz ratio in the following way. As observedin the previous section, let f be a function orthogonal to the constant function.
Then(1f, f )≥ k − λ1 (X)(f, f )
for a k-regular graph. Fix a subset A of X. If we set
|X\A| if x ∈ A
f (x) =−|A| if x ∈/Athen it is easily seen that (f, f0 ) = 0. On the other hand, a direct calculationshows that(f, f ) = |X||A||X\A|.
By using the formula(1f, f ) =1 X(f (x) − f (y))22 (x,y)∈E

we easily check that
(1f, f ) = |X|2 |∂A|
so that by the Rayleigh-Ritz theorem we obtain
|∂A|
|X\A|
≥ (k − λ1 (X))
.
|A|
|X|
By the definition of an expander, we consider only subsets A with |A| ≤ |X|/2,
so that (k − λ1 )/2 is an expander constant for X. Thus, making λ1 as small as
possible gives us good expander graphs. By the Alon-Boppana theorem, wecannot do better than√λ1 (X) ≤ λ(X) ≤ 2 k − 1.
Hence, Ramanujan graphs also make good expanders.

Ramanujan Graphs

17

5. Explicit Ramanujan graphs
In this section, we give a brief outline of the explicit construction of Ramanujan
graphs due to Lubotzky, Phillips and Sarnak [12]. Let p and q be unequal
primes p, q ≡ 1( mod 4). Let u be an integer so that u2 ≡ −1( mod q).
By a classical formula of Jacobi, we know that there are 8(p + 1) solutionsv = (a, b, c, d) such that a 2 + b2 + c2 + d 2 = p. Among these, there areexactly p + 1 with a > 0 and b, c, d even, as is easily shown. To each such v
we associate the matrix
a + ub c + udṽ =−c + ud a − ubwhich gives us p + 1 matrices in P GL2 (Z/qZ). We let S be the set of thesematrices ṽ and take G = P GL2 (Z/qZ). In [LPS], it is shown that the Cayley
graphs X(G, S) are Ramanujan graphs. As we vary q, we get an infinite familyof such graphs, all p + 1-regular.
6. Counting walks in regular graphs
If A is the adjacency matrix of X, it is clear that the (x, y)-th co-ordinateof Ar enumerates the number of walks of length r from x to y. We will beinterested in proper walks, that is, walks which do not have back-tracking. We
are interested in counting the number of proper walks of length r in a k-regulargraph. Let Ar denote the matrix whose (x, y)-th entry will be the number ofproper walks from x to y. Then, A0 = I and A1 = A and clearly
A2 = A2 + kI
since A2 encodes the number of proper walks of length 2. Inductively, it isclear that
A1 Ar = Ar+1 + (k − 1)Ar−1 ,since the left hand side enumerates walks of length r + 1 which are extended
from proper walks of length r and the right side enumerates first the proper
walks of length r + 1 and proper walks of length r − 1 which are extended to‘improper’ walks of length r.
This recursion allows us to deduce the following identity of formal power
series:
Proposition 11.
∞
X

!
Ar t

r


I − At + (k − 1)t 2 I = (1 − t 2 )I.

r=0

From this result, it is possible to establish the rationality of the zeta functionof a regular graph (see Theorem 12 below).

18

M. Ram Murty
7. The Ihara zeta function

Let X be a k-regular graph and set q = k − 1. Motivated by the theory of theSelberg zeta function, Ihara [8] was led to make the following definitions andconstruct the graph-theoretic analogue of it as follows. A proper walk whose
endpoints are equal is called a closed geodesic. If γ is a closed geodesic, wedenote by γ r the closed geodesic obtained by repeating the walk γ r times.
A closed geodesic which is not the power of another one is called a prime
geodesic. We define an equivalence relation on the closed geodesics as follows.
(x0 , ..., xn ) and (y0 , ..., ym ) are equivalent if and only if m = n and there is a dsuch that yi = xi+d for all i (and the subscripts are interpreted modulo n). An
equivalence class of a prime geodesic is called a prime geodesic cycle. Ihara[Ih] then defines the zeta functionY−1
ZX (s) =1 − q −s`(p)pwhere the product is over all prime geodesic cycles p and `(p) is the lengthof p.
Ihara proves the following theorem:
Theorem 12.

For g = (q − 1)|X|/2, we have

ZX (s) = (1 − u2 )−g det(I − Au + qu2 I )−1 ,u = q −s .

Moreover, ZX (s) satisfies the “Riemann hypothesis” (that is, all the singularpoints in the region 0 < <(s) < 1 lie on <(s) = 1/2 ) if and only if X is a
Ramanujan graph.
Proof. (Sketch) We assume that the zeta function has the shape given (see[25]) and show that it satisfies the Riemann hypothesis if and only if X is
Ramanujan. Let φ(z) = det(zI − A) be the characteristic polynomial of A.
If we set z = (1 + qu2 )/u, then the singular points of ZX (s) arise from thezeros of φ(z). First suppose that ZX (s) satisfies the “Riemann hypothesis.”Then, for any singular point s0 , we have q|u0 |2 = 1 where u0 = q −s0 . Let
z0 = (1 + qu20 )/u0 be the corresponding eigenvalue of A. Since,zu
u + q|u|2 u(1 + qu2 )u
=
=
u
uu
|u|2
we see that√|z0 | = q|u0 + u0 | ≤ 2 q√
so that X is Ramanujan. Conversely, if X is Ramanujan, |z0 | ≤ 2 q for any
eigenvalue z0 of A. As z0 is real, this means z02 ≤ 4q andqz0 ± z02 − 4q
u0 :=
2q

Ramanujan Graphs

19√either is not real or u0 = ±1/ q. If the latter is the case, we are done. In theformer case, we have as before
z0 =u0 + q|u0 |2 u0|u0 |2and the reality of z0 forces q|u0 |2 = 1, as desired.

2

Hashimoto [6], as well as Stark and Terras [23] have defined a zeta function
for an arbitrary graph and established its rationality. The definition of this zetafunction is simple enough. Let Nr be the number of closed walks γ of length
r so that neither γ nor γ 2 have backtracking. Then, the zeta function of thegraph X is defined as!
∞X
Nr t r.
ZX (t) = expr
r=1This definition is very similar to the zeta function of an algebraic variety. It
would be interesting to interpret the singularities of ZX (t) in terms of propertiesof the graph. For instance, these zeta functions have a pole at t = 1 andHashimoto [6] has shown that the residue at t = 1 is related to the numberof spanning trees of the graph X. Thus, this number is the graph-theoretic
analogue of the class number of an algebraic number field. These constructions
raise the intriguing question of whether there is a generalization of the notionof a graph to that of a ‘supergraph’ whose zeta function would (in some cases)
coincide with those higher dimensional zeta functions of varieties.

Acknowledgments
I would like to thank David Gregory for his careful reading of the first draft ofthis paper.

References[1] L. Babai, Spectra of Cayley Graphs, Journal of Combinatorial Theory, Series B 27
(1979), 180–189.
[2] F. Bien, Constuction of Telephone Networks by Group Representations, Notices of
the Amer. Math. Society, 36 (1989), No. 1, 5–22.
[3] F.R.K. Chung, Diameters and Eigenvalues, Journal of the American Math. Society, 2(1989), 187–196.
[4] P. Diaconis and M. Shahshahani, Generating a Random Permutation with RandomTranspositions, Zeit. für Wahrscheinlichkeitstheorie verw. Gebiete, 57 (1981), 159–
179.
[5] J. Friedman, On the second eigenvalue and random walks in random d-regular graphs,
Combinatorica, 11 (1991), 331–362.

20

M. Ram Murty[6] K. I. Hashimoto, Zeta functions of finite graphs and representations of p-adic groups,
Advanced Studies in Pure Math., 15 (1989), 211–280.
[7] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
[8] 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.
[9] W.C. Winnie Li, Number Theory with Applications, Series of University Mathematics,
Vol. 7, World Scientific, 1996.
[10] W.C. Winnie Li, Character sums and abelian Ramanujan graphs, Journal of Number
Theory, 41 (1992), 199–217.
[11] W.C. Winnie Li, Recent developments in automorphic forms and applications, Number
Theory for the Millenium, Volume 2, edited by M.A. Bennett, B.C. Berndt, N. Boston,
H.G. Diamond, A.J. Hildebrand, and W. Philipp, 2002, pp. 331–354, A.K. Peters,
Natick, Massachusetts.
[12] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan Graphs, Combinatorica, 9 (1988),
261–277.
[13] A. Lubotzky, Discrete Graphs, Expanding Graphs and Invariant Measures, Progressin Mathematics, 125 Birkhäuser, 1994.
[14] G.A. Margulis, Explicit group-theoretical constructions of combinatorial schemes andtheir application to the design of expanders and concentrators, J. Probl. Inf. Transm.
24 No. 1, (1988), 39–46.
[15] M. Morgenstern, Existence and explicit construction of q + 1 regular Ramanujan
graphs for every prime power q, J. Comb. Theory, ser. B, 62(1994), 44–62.
[16] M. Ram Murty, Problems in Analytic Number Theory, Graduate Texts in Mathematics,
206, Springer-Verlag, 2001.
[17] A. Nilli, On the second eigenvalue of a graph, Discrete Math., 91 (1991), 207–210.
[18] A. Pizer, Ramanujan graphs and Hecke operators, Bulletin of the Amer. Math. Soc.,
23(1) (1990), 127–137.
[19] G. Quenell, Spectral diameter estimates for k-regular graphs, Advances in Math., 106(1994), 122–148.
[20] P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Mathematics,
99, Cambridge University Press, 1990.
[21] J.-P. Serre, Répartition asymptotique des valeurs propres de l’opérateur de Hecke Tp ,Journal of the Amer. Math. Society, 10 (1997), no. 1, 75–102.
[22] J.-P. Serre, Majorations de sommes exponentielles, Journées Arithmétques de Caen
(Univ. Caen, Caen 1976), Astérisque 41–42 (1977), 111–126.
[23] H.M. Stark and A. Terras, Zeta functons of finite graphs and coverings, Advances in
Math., 121 (1996), 124–165.
[24] T. Sunada, Fundamental groups and Laplacians, Lecture Notes in Mathematics, 1339
(1988), 248–277, Springer-Verlag.
[25] T. Sunada, L-functions in geometry and some applications, Lecture Notes in Math.,
1201 (1986), Springer-Verlag.
[26] A. Terras, Fourier Analysis on Finite Groups and Applications, London MathematicalSociety Student Texts 43, Cambridge University Press, 1999.
[27] A. Valette, Graphes de Ramanujan, Astérisque, 245 (1997), 247–276.