IAS/Park City Mathematics Series
Volume 12, 2002Ramanujan Graphs and Ramanujan
Hypergraphs
Wen-Ching Winnie Li
Introduction
The Ramanujan conjecture, originated in modular forms and then extended to
representations, concerns the size of eigenvalues. It is a very deep and fascinating
conjecture in number theory. Of the eight lectures on this topic scheduled in the
PCMI 2002 graduate program, half are theoretic, and half are applications oriented.
L. Clozel's four lectures provide representation-theoretic background and the cur-
rent status of the Ramanujan conjecture. Connections of this conjecture with other
topics in representation theory are also discussed there.
The purpose of my two lectures is to show applications of the Ramanujan
conjecture to problems with close ties to the real world. More precisely, we are
going to see how the Ramanujan conjecture, established for GL 2 over Q and GLn
with n ::::: 2 over function fields, are used in the explicit constructions of Ramanujan
graphs and Ramanujan hypergraphs. These are graphs and hypergraphs whose
nontrivial eigenvalues fall in the spectrum of their respective universal cover. The
Ramanujan graphs have good expansion property and families of such graphs have a
variety of important applications in computer science. Their adjacency matrices are
being used by coding theorists to construct good "low density parity check" linear
codes which are easy to decode. Perhaps the adjacency matrices of Ramanujan
hypergraphs could have similar applications.
In the first lecture we explain the spectral theory of regular graphs as a discrete
analogue of the spectral theory of the Laplacian operator, and study the behavior
of the eigenvalues as the graph size increases. This motivates the definition of Ra-
manujan graphs. We shall then review various known constructions of Ramanujan
graphs and discuss the relationship among them. This relationship leads to the dis-
covery of automorphic forms for GL 2 over function fields which are eigenfunctions
of the Hecke operators with eigenvalues given by explicit character sums which are
(^1) Department of Mathematics, Pennsylvania State University, University Park, PA 16803.
E-mail address: wli©math. psu. edu.
This research was supported in part by the NSF grant DMS99- 70651 and NSA grant MDA904-
03-1-0069. The research on Ramanujan hypergraphs was initiated while the author was visiting
the Institute for Advanced Study, Princeton, NJ, in 2000, partially supported by the Ellentuck
Fund.
401