Joint IAS/PU Groups and Dynamics Seminar

Extremal eigenvalues of graphs are of particular interest in theoretical computer science and combinatorics. Specifically, the spectral gap—the difference between the largest and second-largest eigenvalues—measures the expansion properties of a graph. In this talk, I will focus on random d-regular graphs.
I will begin by providing background on the eigenvalues of random d-regular graphs and their connections to random matrix theory. In the second part of the talk, I will discuss our recent results on eigenvalue rigidity and edge universality for these graphs. Eigenvalue rigidity asserts that, with high probability, each eigenvalue concentrates around its classical location as predicted by the Kesten-McKay distribution. Edge universality states that the second-largest eigenvalue and the smallest eigenvalue of random d-regular graphs converge to the Tracy-Widom distribution from the Gaussian Orthogonal Ensemble. Consequently, approximately 69% of d-regular graphs are Ramanujan graphs. This work is based on joint work with Theo McKenzie and Horng-Tzer Yau.