The Spectral Edge of Constant Degree Erdős–Rényi Graphs
Authors:
- 19 May 2025
- journal article
- Published by Wiley in Random Structures & Algorithms
- Vol. 66 (3)
Abstract
We show that for an Erdős–Rényi graph on vertices with expected degree satisfying , the largest eigenvalues can be precisely determined by small neighborhoods around vertices of close to maximal degree. Moreover, under the added condition that , the corresponding eigenvectors are localized, in that the mass of the eigenvector decays exponentially away from the high degree vertex. This dependence on local neighborhoods implies that the edge eigenvalues converge to a Poisson point process. These theorems extend a result of Alt, Ducatez, and Knowles, who showed the same behavior for satisfying and answer a question of Guionnet. To achieve high accuracy in the constant degree regime, instead of comparing the true eigenvector to that of a tree with more regularity, we examine the eigenvector equation at each vertex in a ball to deduce localization of the eigenvector and derive a continued fraction formula for the eigenvalue. This formula can be applied to any tree and could be of independent interest, especially for rooted trees with large central degree.Keywords
Funding Information
- Citadel Foundation
- National Science Foundation (DGE‐1752814, DMS‐2212881)
This publication has 41 references indexed in Scilit:
- Delocalization Transition for Critical Erdős–Rényi GraphsCommunications in Mathematical Physics, 2021
- Outliers in spectrum of sparse Wigner matricesRandom Structures & Algorithms, 2020
- Delocalization at Small Energy for Heavy-Tailed Random MatricesCommunications in Mathematical Physics, 2017
- Central Limit Theorems for Linear Statistics of Heavy Tailed Random MatricesCommunications in Mathematical Physics, 2014
- A Generalization of Wigner’s LawCommunications in Mathematical Physics, 2006
- Spectral techniques in graph algorithms1998
- Concentration of measure and isoperimetric inequalities in product spacesPublications mathématiques de l'IHÉS, 1995
- Localization at large disorder and at extreme energies: An elementary derivationsCommunications in Mathematical Physics, 1993
- Absence of diffusion in the Anderson tight binding model for large disorder or low energyCommunications in Mathematical Physics, 1983
- A pure point spectrum of the stochastic one-dimensional schrödinger operatorFunctional Analysis and Its Applications, 1977