School Seminars and Colloquia

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.