ÍâÍøÌìÌÃ

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.

Ìý

Ìý