TY - JOUR
T1 - Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs
AU - HE, Yukun
AU - KNOWLES, Antti
AU - MARCOZZI, Matteo
PY - 2019/9
Y1 - 2019/9
N2 - 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 l2 and l∞ 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.
AB - 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 l2 and l∞ 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.
KW - Eigenvector delocalization
KW - Erdős–Rényi graph
KW - Local law
KW - Sparse random matrix
UR - http://www.scopus.com/inward/record.url?scp=85076742531&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85076742531&origin=recordpage
U2 - 10.1214/19-AOP1339
DO - 10.1214/19-AOP1339
M3 - 21_Publication in refereed journal
VL - 47
SP - 3278
EP - 3302
JO - Annals of Probability
JF - Annals of Probability
SN - 0091-1798
IS - 5
ER -