Extreme eigenvalues of random graphs with growing degrees

-
Jiaoyang Huang, University of Pennsylvania

I will discuss some recent results on extreme eigenvalue of Erdős–Rényi graphs $G(N,p)$ and random $d$-regular graphs. We are interested in the sparse regime, where the average degree is much smaller than the size $N$ of the graph, and meanwhile it grows to infinite with $N$.  For Erdős–Rényi graphs when the average degree $pN\gg N^{1/3}$, extreme eigenvalues have Tracy-Widom fluctuations from random matrix theory. However, when $N^{\epsilon}\le pN\ll N^{1/3}$ the extreme eigenvalues have Gaussian fluctuations, explicitly given by certain subgraph counting quantities. Up to this explicit random shift, we prove the fluctuations of the extreme eigenvalues are still given by the Tracy-Widom distribution. The gaps between extreme eigenvalues have the same law as those of the Airy point process. For random $d$-regular graphs, the fluctuations of those subgraph counting quantities are negligible. When $N^{\epsilon}\le d\ll N^{1/3}$, we prove the fluctuation of their extreme eigenvalues converges to the Tracy-Widom distribution.  As a consequence, in the same regime of $d$, about 69% of all $d$-regular graphs have the second-largest eigenvalue strictly less than $2\sqrt{d-1}$. Our proof is based on constructing a higher order self-consistent equation for the Stieltjes transform of the empirical eigenvalue distributions.

This is based on joint works with Horng-Tzer Yau.