Extreme eigenvalue distributions of sparse random graphs

Seminar: 
Combinatorics Seminar
Event time: 
Thursday, November 14, 2019 - 4:00pm
Location: 
DL 431
Speaker: 
Jiaoyang Huang
Speaker affiliation: 
IAS
Event description: 

I will discuss the extreme eigenvalue distributions of adjacency matrices of sparse random graphs, in particular the Erdos-Renyi graphs $G(N,p)$ and the random $d$-regular graphs. For Erdos-Renyi 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.

Research Area(s):