EXTREMAL EIGENVALUES OF CRITICAL ERDOS-RENYI GRAPHS

• 成果类型: Article
• 署名作者: Alt, Johannes; Ducatez, Raphael; Knowles, Antti
• 署名单位: University of Geneva
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/20-AOP1483
• 发表日期: 2021
• 页码: 1347-1401
• 关键词: spectral techniques

摘要

We complete the analysis of the extremal eigenvalues of the adjacency matrix A of the Erdos-Renyi graph G(N, d/N) in the critical regime d asymptotic to log N of the transition uncovered in (Ann. Inst. Henri Poincare Probab. Stat. 56 (2020) 2141-2161; Ann. Probab. 47 (2019) 1653-1676), where the regimes d >> log N and d << log N were studied. We establish a one-to-one correspondence between vertices of degree at least 2d and nontrivial (excluding the trivial top eigenvalue) eigenvalues of A/root d outside of the asymptotic bulk [-2, 2]. This correspondence implies that the transition characterized by the appearance of the eigenvalues outside of the asymptotic bulk takes place at the critical value d = d(*) = 1/log 4-1 log N. For d < d(*), we obtain rigidity bounds on the locations of all eigenvalues outside the interval [-2, 2], and for d > d(*), we show that no such eigenvalues exist. All of our estimates are quantitative with polynomial error probabilities. Our proof is based on a tridiagonal representation of the adjacency matrix and on a detailed analysis of the geometry of the neighbourhood of the large degree vertices. An important ingredient in our estimates is a matrix inequality obtained via the associated nonbacktracking matrix and an Ihara-Bass formula (Ann. Inst. Henri Poincare Probab. Stat. 56 (2020) 2141-2161). Our argument also applies to sparse Wigner matrices, defined as the Hadamard product of A and a Wigner matrix, in which case the role of the degrees is replaced by the squares of the l(2)-norms of the rows.