# 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.