School Seminars and Colloquia

Ramanujan Graphs (II)

Discrete Structures and Algorithms (Reading Group)

by Sanming Zhou


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

Abstract: A well-known result due to Alon and Boppana asserts that, for any sequence $(X_m)$ of finite connected $k$-regular graphs with order tending to $\infty$ as $m \rightarrow \infty$, the lim inf of the second largest eigenvalues of $X_m$'s is greater than or equal to $2\sqrt{k-1}$. We will discuss a generalisation of this result, due to J.-P. Serre, which asserts that for any $\epsilon > 0$, any finite connected $k$-regular graph has a positive proportion of eigenvalues in the interval $[(2-\epsilon) \sqrt{k-1}, k]$. If time permits, we may also discuss a counterpart result for the lower end of the spectrum which involves the girth of the graphs in the sequence.