210 R. Brooks
Our expectation is that the background of the students in complex analysis
and Riemann surfaces is perhaps the weakest point. For that purpose, the
primary purpose of the notes will be to supply the reader with the necessary
background in this area. Another area that we expect the students to be
relatively weak is in probability theory. As this was the part of the material
that came least naturally to us, we will also try to be fairly explicit here. Our
plan is to post these notes on our web site as well as on the web site of the
IHP, in a timely manner as the notes are written. We encourage the reader to
check for updates and additions.
It is a pleasure to thank Thierry Coulhon and the organizers of the special
trimester “Noyaux de Chaleur” for the invitation to participate in the special
semester and to deliver these lectures.
12.2 An Opening Question
It has long been an interest of mine to pass between graphs and manifolds.
The standard picture is in some sense quite clear and elegant. Nonetheless, it
seems to me that there is much that can be added to the standard picture.
To give you an idea of the problem, let us consider a family of graphsXp,q
considered by Lubotsky, Phillips, and Sarnak. They are indexed by two prime
numberpandq, and arep+ 1-regular graphs that are Cayley graphs (with re-
spect to some nice choice of generators) of eitherPSL(2,Z/q)orPGL(2,Z/q),
depending on certain properties ofpandq. They have the property that
their first eigenvalue is as large as possible, and for that reason were called
Ramanujan graphsby L-P-S.
Fig. 12.1.The graphX^23 accordingtoSarnak