Extreme eigenvalue distributions of sparse random graphs
Presenter
November 15, 2019
Abstract
I will discuss the extreme eigenvalue distributions of adjacency matrices of sparse random graphs, in particular the Erd{\H o}s-R{\'e}nyi graphs $G(N,p)$ and the random $d$-regular graphs. For Erd{\H o}s-R{\'e}nyi graphs, there is a crossover in the behavior of the extreme eigenvalues. When the average degree $Np$ is much larger than $N^{1/3}$, the extreme eigenvalues have asymptotically Tracy-Widom fluctuations, the same as Gaussian orthogonal ensemble. However, when $N^{2/9}\ll Np\ll N^{1/3}$ the extreme eigenvalues have asymptotically Gaussian fluctuations. The extreme eigenvalues of random $d$-regular graphs are more rigid, we prove on the regime $N^{2/9}\ll d\ll N^{1/3}$ the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by the Tracy-Widom statistics. Thus, in the same regime of $d$, $52\%$ of all $d$-regular graphs have the second-largest eigenvalue strictly less than $2\sqrt{d-1}$. These are based on joint works with Roland Bauerschmidt, Antti Knowles, Benjamin Landon and Horng-Tzer Yau.