Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, February 18, 2020 - 3:00pm

Jiaoyang Huang

Institute for Advanced Study

Location

University of Pennsylvania

David Rittenhouse Lab 4C8

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 Bauerschmids, Antti Knowles, Benjamin Landon and Horng-Tzer Yau.