Seminar in Elementary Number Theory, Group
Theory, and Ramanujan Graphs
Spring 2025
About the seminar
This seminar is dedicated to the construction of expander graphs, which are sparse yet highly connected graphs with wide-ranging applications in computer science. Specifically, we will focus on Ramanujan graphs, which are optimal expanders. We will establish the expansion properties of classical and elegant constructions of Ramanujan graphs using elementary number theory and group theory, including some elements of representation theory, which we will develop from the ground up. We will mostly follow this book by Davidoff, Sarnak, and Valette, which shares its title with this seminar.
When & where
Thursdays 10:00-12:00. Location: TBD.
Tentative plan
As mentioned, we will mostly follow this book by Davidoff, Sarnak, and Valette, covering most of it. Some of the topics may be skipped if the number of students is lower than expected. The list of lectures is roughly as follows:
Chapter 1. Graph Theory (2 weeks; by me)
-
The adjacency matrix and its spectrum
-
Inequalities on the spectral gap
-
Asymptotic behavior of eigenvalues
-
Independence number and chromatic number
-
Large girth and large chromatic number
Chapter 2. Number Theory (3 weeks)
-
Sum of two squares
-
Quadratic reciprocity
-
Sum of four squares
-
Quaternions
-
The arithmetic of integer quaternions
Chapter 3. PSL_2(q) (5 weeks)
-
Group theory 101 (by me)
-
Simplicity
-
Structure of subgroups
-
Representation theory of finite groups (by me)
-
Degrees of representations of PSL_2(q)
Chapter 4. Explicit construction of our graphs (3 weeks)
-
Cayley graphs
-
Construction
-
Girth and connectedness
-
Spectral estimates