Ramanujan Property and Edge Universality of Random Regular Graphs

Explore a mathematics seminar presentation that delves into the fascinating world of random regular graphs and their eigenvalue properties. Learn about the significance of spectral gaps in theoretical computer science and combinatorics, with particular emphasis on how these gaps measure graph expansion properties. Discover the fundamental concepts of random d-regular graphs and their connection to random matrix theory, followed by an in-depth examination of recent findings on eigenvalue rigidity and edge universality. Understand how eigenvalue rigidity demonstrates high-probability concentration around classical Kesten-McKay distribution locations, while edge universality reveals the convergence of second-largest and smallest eigenvalues to the Tracy-Widom distribution from the Gaussian Orthogonal Ensemble. Gain insights into the remarkable conclusion that approximately 69% of d-regular graphs are Ramanujan graphs, based on collaborative research with Theo McKenzie and Horng-Tzer Yau.