Repository logo
 

Edge rigidity and universality of random regular graphs of intermediate degree

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Bauerschmidt, Roland  ORCID logo  https://orcid.org/0000-0001-7453-2737
Huang, J 
Knowles, A 
Yau, HT 

Abstract

For random d-regular graphs on N vertices with 1≪dN2/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\H{o}s-R'enyi graphs of the same average degree. As a first application, for 1≪dN2/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/9dN1/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 $2 \sqrt{d

  • 1}$.

Description

Keywords

math.PR, math.PR, 60B20, 15B52, 05C80

Journal Title

Geometric and Functional Analysis

Conference Name

Journal ISSN

1016-443X
1420-8970

Volume Title

30

Publisher

Springer Science and Business Media LLC

Rights

All rights reserved
Sponsorship
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.