Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs

Tuesday, 28 August, 2018

Published in: 

arXiv:1808.09437

We prove a local law for the adjacency matrix of the Erd\H{o}s-R\'enyi graph G(N,p) in the supercritical regime pN \geq 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 \cite{EKYY1} 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 \ell^2 and \ell^\infty norms of the coefficients with combinatorial factors, allowing us to prove strong enough concentration down to the critical scale pN = O(\log N).

Author(s): 

Yukun He
Antti Knowles
Matteo Marcozzi