1549380232-Automorphic_Forms_and_Applications__Sarnak_

LECTURE 1. RAMANUJAN GRAPHS 405

Again, if each x in Um+l h as one neighbor in Um and q neighbors in Um+ 2 , then

Ag(x)= (~)m+q(~)m+2 = (~)m+l (-Jq-q~) =g(x)(-20]),

and a similar argument holds. Suppose some x E Um+l has less than q neighbors

in Um+ 2. If x has a neighbor lying in Um+l, then this makes the absolute value of

Ag(x) smaller, which is undesirable. Note that in this case X contains a cycle of

odd length (at most 2m + 3). If x has more than one neighbor lying in Um, then

this only makes the absolute value of Ag(x) larger, which is fine. In this case we see

a cycle of even length. This explains the assumption (C). Of course the theorem

still holds as long as there are not too many odd cycles of short length.

Remark. To each graph Xj we associate the normalized probability measure μ(Xj)

supported at the spectrum of Xj, that is,

1

μ(Xj) = IXjl L 8>-./2 v'k=I>

>-. eigenvalue of X j

supporte dm. [ - v'k=I, k v'k=I k l

and let μ be the limit of a subsequence μ(XjJ as Ji ---> oo. Serre observed that

condition (C) implies that μis symmetric, i.e. μ(x) = μ(-x). See the presenter's

comments in [20].

The universal cover of k-regular graphs is the k-regular infinite tree~' which is
a discrete analogue of the Poincare upper half plane identified with SL2(1R)/S02(1R).
The adjacency operator A on ~ is the discrete analogue of the Laplace operator.

Its spectrum is [-2 Jk=l", 2 ../k - l]. In the event that q = k-1 is a prime power,

there is a local field F with q elements in its residue field such that ~ is isomorphic
to the natural tree structure on the coset space PGL 2 (F) /PGL2 ( 0 F) of equivalence
classes of rank 2 lattices over F, where OF denotes the ring of integers of F. The
adjacency operator A can be identified with the Hecke operator T which maps a
function f on PGL2(F)/PGL2(0F) to

Tf([g]) = L f([g (~ ~)]) + f([g G ~)]), g E GL2(F).

uEOp

Here, for g E GL 2 (F), [g] denotes the coset of g in PGL 2 (F)/PGL2(0F), 7f is
a uniformizer of F and p F = 7f 0 F is the maximal ideal of 0 F. The Plancherel
measure μk on~' normalized with support [-2, 2 ], is
k
μk = (../k - 1 + 1)2 - x2 μsT
v'k=I
where μsT is the Sato-Tate measure

(1.3)

1g2

μsT = - 1 - - dx.

7f 4

Observe that the lim inf>.+ and li m sup.>. - bounds discussed before are the two

boundary points of the spectrum of ~.

Definition. A k-regular graph X is called a Ramanujan graph if

.>.+(x)::::; 2v'k"=l" and >--(x) 2: -2v'k"=l",

that is, the spectrum of X other than ±k is contained in the spectrum of the
k-regular infinite tree~-