LOCAL LAW AND COMPLETE EIGENVECTOR DELOCALIZATION FOR SUPERCRITICAL ERDŐS–RÉNYI GRAPHS

We prove a local law for the adjacency matrix of the Erdős–Rényi graph G(N, p) in the supercritical regime pN ≥ C log N where G(N, p) has with high probability no isolated vertices. In the same regime, we also prove the complete delocalization of the eigenvectors. Both results are false in the compl...

Full description

Saved in:
Bibliographic Details
Published in:The Annals of probability 2019-09, Vol.47 (5), p.3278-3302
Main Authors: He, Yukun, Knowles, Antti, Marcozzi, Matteo
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove a local law for the adjacency matrix of the Erdős–Rényi graph G(N, p) in the supercritical regime pN ≥ C log N where G(N, p) has with high probability no isolated vertices. In the same regime, we also prove the complete delocalization of the eigenvectors. Both results are false in the complementary subcritical regime. Our result improves the corresponding results from (Ann. Probab. 41 (2013) 2279–2375) by extending them all the way down to the critical scale pN = O(log N). A key ingredient of our proof is a new family of multilinear large deviation estimates for sparse random vectors, which carefully balance mixed ℓ² and ℓ∞ norms of the coefficients with combinatorial factors, allowing us to prove strong enough concentration down to the critical scale pN = O(log N). These estimates are of independent interest and we expect them to be more generally useful in the analysis of very sparse random matrices.
ISSN:0091-1798
2168-894X
DOI:10.1214/19-AOP1339