LARGEST EIGENVALUES OF SPARSE INHOMOGENEOUS ERDOS-RENYI GRAPHS

• 成果类型: Article
• 署名作者: Benaych-Georges, Florent; Bordenave, Charles; Knowles, Antti
• 署名单位: Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite; Universite Federale Toulouse Midi-Pyrenees (ComUE); Universite de Toulouse; Institut National des Sciences Appliquees de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); University of Geneva
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/18-AOP1293
• 发表日期: 2019
• 页码: 1653-1676

摘要

We consider inhomogeneous Erdos-Renyi graphs. We suppose that the maximal mean degree d satisfies d << log n. We characterise the asymptotic behaviour of the (1-omicron)(n)(1) largest eigenvalues of the adjacency matrix and its centred version. We prove that these extreme eigenvalues are governed at first order by the largest degrees and, for the adjacency matrix, by the nonzero eigenvalues of the expectation matrix. Our results show that the extreme eigenvalues exhibit a novel behaviour which in particular rules out their convergence to a nondegenerate point process. Together with the companion paper [Benaych-Georges, Bordenave and Knowles (2017)], where we analyse the extreme eigenvalues in the complementary regime d >> log n, this establishes a crossover in the behaviour of the extreme eigenvalues around d similar to log n. Our proof relies on a tail estimate for the Poisson approximation of an inhomogeneous sum of independent Bernoulli random variables, as well as on an estimate on the operator norm of a pruned graph due to Le, Levina, and Vershynin from [Random Structures Algorithms 51 (2017) 538-561].