Extreme eigenvalues of adjacency matrices of random $d$-regular graphs
Location
I will discuss some results on extreme eigenvalue distributions of adjacency matrices of random $d$-regular graphs, which are believed to be universal following the Tracy-Widom distribution.
In the first part of the talk I will present the results on random $d$-regular graphs, where $d$ grows with the size $N$ of the graph, we confirmed that on the regime $N^{2/9}<< d<< N^{1/3}$ the extremal eigenvalues after proper rescaling are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by the Tracy-Widom statistics. Thus, in the same regime of $d$, about fifty two percent of all $d$-regular graphs have the second-largest eigenvalue strictly less than $2\sqrt{d-1}$. In the second part of the talk, I will focus on random $d$-regular graphs with fixed $d>=3$, and give a new proof of Alon's second eigenvalue conjecture that with high probability, the second eigenvalue of a random $d$-regular graph is bounded by $2\sqrt{d-1}+o(1)$, where we can show that the error term is polynomially small in the size of the graph.
These are based on joint works with Roland Bauerschmids, Antti Knowles and Horng-Tzer Yau.