Speaker
Description
The second largest eigenvalue of a graph's adjacency matrix captures important structure and spectral properties including connectivity and expansion. From the Alon-Boppana theorem, we know that if $\theta<2\sqrt{k-1}$, then there are only finitely many $k$-regular graphs with the second largest eigenvalue at most $\theta$. This motivates the following natural question posed by Richey, Stover, and Shutty in 2013. Given $k\geq 3$ and $\theta<2\sqrt{k-1}$, what is the maximum number of vertices $v(k,\theta)$ of a $k$-regular graph $G$ with $\lambda_2(G)\leq \theta$? This problem can be seen as a spectral version of the Moore (or degree-diameter) problem. In this talk, I will present recent progress on this question. This is joint work with Cioab\u{a}, Nozaki, and Xiang.