School Seminars and Colloquia

Ramanujan Graphs (I)

Discrete Structures and Algorithms (Reading Group)

by Sanming Zhou

Institution: The University of Melbourne
Date: Wed 17th October 2012
Time: 10:00 AM
Location: Room 107, Richard Berry Building

Abstract: Ramanujan graphs are a family of expanders which achieve the largest possible spectral gap and thus have the best possible expansion from a spectral point of view.

Starting from this week we will discuss the celebrated family of Ramanujan graphs constructed by Lubotzky, Phillips and Sarnak. We will mainly follow the treatment in the book `Elementary Number Theory, Group Theory, and Ramanujan Graphs' (G. Davidoff, P. Sarnak and A. Valette, Cambridge University Press, 2003). In this first presentation, we will give an overview of this book and review a few basic facts about the spectrum of a regular graph, including the Alon-Milman and Dodziuk inequalities and the Alon-Boppana bound. We will also discuss a few results which are preparations for the proof of a generalisation of the Alon-Boppana bound due to Serre.