# Ramanujan Graphs (IV)

*Discrete Structures and Algorithms (Reading Group)*

*by Sanming Zhou*

*Institution:*The University of Melbourne

*Date: Wed 7th November 2012*

*Time: 10:00 AM*

*Location: Room 107, Richard Berry Building*

*Abstract*: We will discuss the following result and its proof: Let $X_m, m \ge 1$ be a sequence of finite, connect, $k$-regular graphs with girth tending to infinity as $m$ goes to infinity. Then for any $\epsilon > 0$ there exists a positive constant $C$ such that the number of eigenvalues of $X_m$ in the interval $[-k, (-2+\epsilon) \sqrt{k-1}]$ is as least $C |V(X_m)|$. We will also discuss two results connecting the eigenvalues and the independence and chromatic numbers of a regular graph.