Fluctuations of extreme eigenvalues of sparse Erdős–Rényi graphs

Abstract

Abstract We consider a class of sparse random matrices which includes the adjacency matrix of the Erdős–Rényi graph $${{\mathcal {G}}}(N,p)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>,</mml:mo> <mml:mi>p</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We show that if $$N^{\varepsilon } \leqslant Np \leqslant N^{1/3-\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>N</mml:mi> <mml:mi>ε</mml:mi> </mml:msup> <mml:mo>⩽</mml:mo> <mml:mi>N</mml:mi> <mml:mi>p</mml:mi> <mml:mo>⩽</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> then all nontrivial eigenvalues away from 0 have asymptotically Gaussian fluctuations. These fluctuations are governed by a single random variable, which has the interpretation of the total degree of the graph. This extends the result (Huang et al. in Ann Prob 48:916–962, 2020) on the fluctuations of the extreme eigenvalues from $$Np \geqslant N^{2/9 + \varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>p</mml:mi> <mml:mo>⩾</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>9</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> down to the optimal scale $$Np \geqslant N^{\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>p</mml:mi> <mml:mo>⩾</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mi>ε</mml:mi> </mml:msup> </mml:mrow> </mml:math> . The main technical achievement of our proof is a rigidity bound of accuracy $$N^{-1/2-\varepsilon } (Np)^{-1/2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mi>p</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> for the extreme eigenvalues, which avoids the $$(Np)^{-1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mi>p</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:math> -expansions from Erdős et al. (Ann Prob 41:2279–2375, 2013), Huang et al. (2020) and Lee and Schnelli (Prob Theor Rel Fields 171:543–616, 2018). Our result is the last missing piece, added to Erdős et al. (Commun Math Phys 314:587–640, 2012), He (Bulk eigenvalue fluctuations of sparse random matrices. arXiv:1904.07140 ), Huang et al. (2020) and Lee and Schnelli (2018), of a complete description of the eigenvalue fluctuations of sparse random matrices for $$Np \geqslant N^{\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>N</mml:mi> <mml:mi>p</mml:mi> <mml:mo>⩾</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mi>ε</mml:mi> </mml:msup> </mml:mrow> </mml:math> .

Topics & Concepts