1549380232-Automorphic_Forms_and_Applications__Sarnak_

Lecture 1. Ramanujan graphs and connections with number theory

1.1. Spectral theory of regular graphs

The structure of a finite graph X on n vertices is completely recorded in its adja-

cency matrix A = A(X), which is an n x n matrix with rows and columns para-

metrized by the vertices of X such that the vv' -th entry gives the number of edges

from vertex v to vertex v'. We shall regard A as an operator which maps a function

f defined on the vertices of X to the function Af given by

Af(v) = L f(v').

v~v'

If X is k-regular and undirected, that is, every vertex has exactly k neighbors,
then A is symmetric and each row sums to k. All eigenvalues of A are real and lie
between k and -k; they a re called the spectrum of X. The multiplicity of k as an

eigenvalue is the number of connected components of X, and -k is an eigenvalu e

if and only if X is bipartite. Thus we are interested in the eigenvalues of X which
li e strictly between k and -k. Define

.+(X) = the largest eigenvalue of X which is< k,
.-(x) = the smallest eigenvalue of X which is> - k.
Let { Xj} be a family of k-regular connected undirected graphs such that IXj I ---->
oo as j----> oo. We study the behavior of >.±(Xj)·

Theorem 1.1. [Alon-Boppana]

liminf >.+(xj)?: 2 Jk"=l.

IX; 1 --->oo

There are several proofs of this result.

(1) [Lubotzky-Phillips-Sarnak [25]]. They gave a lower bound of >.+(X)^2 n in terms

of the number of closed p aths of length 2n through a point on a k-regular

infinite tree.

(2) [Serre [33], [34]]. Using orthogonal polynomials, he proved that given E > 0,

there is a constant c = c( E, k) such that for every k-regular graph X , the

number of eigenvalues>-of X with A?: (2 - E)Jk=l is at least c IXI.

403