Applied Mathematical Seminar31: Spectral gap of dense random regular graphs

Seminar| Institute of Mathematical Sciences

Abstract: Let A be the adjacency matrix of a random d-regular graph on N vertices. For N^(2/3)≪d≤N/2, we prove optimal rigidity estimates of the extreme eigenvalues of A, which in particular imply that the graph is Ramanujian with very high probability. In the same regime of d, we also show that the extreme eigenvalues have Tracy-Widom fluctuations.