Edge rigidity and universality of random regular graphs of intermediate degree
Geometric and Functional Analysis
MetadataShow full item record
Bauerschmidt, R., Huang, J., Knowles, A., & Yau, H. (2020). Edge rigidity and universality of random regular graphs of intermediate degree. Geometric and Functional Analysis, 30 (3), 693-769. https://doi.org/10.1007/s00039-020-00538-0
© 2020, Springer Nature Switzerland AG. For random d-regular graphs on N vertices with 1 ≪ d≪ N2 / 3, we develop a d- 1 / 2 expansion of the local eigenvalue distribution about the Kesten–McKay law up to order d- 3. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of Erdős–Rényi graphs of the same average degree. As a first application, for 1 ≪ d≪ N2 / 3, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by (2+o(1))d-1. As a second application, for N2 / 9≪ d≪ N1 / 3, we prove that the extremal eigenvalues are concentrated at scale N- 2 / 3 and their fluctuations are governed by Tracy–Widom statistics. Thus, in the same regime of d, 52 % of all d-regular graphs have second-largest eigenvalue strictly less than 2d-1.
The work of J.H. is supported by the Institute for Advanced Study. A.K. gratefully acknowledges funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 715539_RandMat) and from the Swiss National Science Foundation through the SwissMAP grant. The work of H.-T.Y. is partially supported by NSF Grants DMS-1606305 and DMS-1855509, and a Simons Investigator award.
External DOI: https://doi.org/10.1007/s00039-020-00538-0
This record's URL: https://www.repository.cam.ac.uk/handle/1810/309395
All rights reserved