Edge rigidity and universality of random regular graphs of intermediate degree

Roland Bauerschmidt, Jiaoyang Huang, Antti Knowles, Horng Tzer Yau

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)693-769
Number of pages77
JournalGeometric and Functional Analysis
Issue number3
StatePublished - Jun 1 2020

ASJC Scopus subject areas

  • Analysis
  • Geometry and Topology


Dive into the research topics of 'Edge rigidity and universality of random regular graphs of intermediate degree'. Together they form a unique fingerprint.

Cite this