TY - JOUR

T1 - Edge rigidity and universality of random regular graphs of intermediate degree

AU - Bauerschmidt, Roland

AU - Huang, Jiaoyang

AU - Knowles, Antti

AU - Yau, Horng Tzer

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020/6/1

Y1 - 2020/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85088154771&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85088154771&partnerID=8YFLogxK

U2 - 10.1007/s00039-020-00538-0

DO - 10.1007/s00039-020-00538-0

M3 - Article

AN - SCOPUS:85088154771

SN - 1016-443X

VL - 30

SP - 693

EP - 769

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 3

ER -