Upper tail of the spectral radius of sparse Erdos-Renyi graphs

• 成果类型: Article
• 署名作者: Basak, Anirban
• 署名单位: Tata Institute of Fundamental Research (TIFR); International Centre for Theoretical Sciences, Bengaluru
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-023-01232-6
• 发表日期: 2023
• 页码: 885-947
• 关键词: large deviation principle; LARGEST EIGENVALUE; wigner matrices; complexity; edge

摘要

We consider an Erdos-Renyi graph G(n, p) on n vertices with edge probability p such that log n log log n np n1/2-o(1), () and derive the upper tail large deviations of.(G(n, p)), the largest eigenvalue of its adjacency matrix. Within this regime we show that, for p n -2/3 the log-probability of the upper tail event of.(G(n, p)) equals to that of planting a clique of an appropriate size (upon ignoring smaller order terms), while for p n -2/3 the same is given by that of the existence of a high degree vertex. We also confirm that in the entire regime () the large deviation probability is asymptotically approximated by the solution of themean-field variational problem, and further identify the typical structure ofG(n, p) conditioned on the upper tail event of.(G(n, p)) in a certain sub-regime of p. For p such that log(np) log n the large deviations of.(G(n, p)) is deduced from those of the homomorphism counts of the cycle graph of length 2t, Hom(C2t, G(n, p)), for t 3 and p such that n1/2-o(1) np n1/t. In this latter regime the typical structure of G(n, p) conditioned on the upper tail of Hom(C2t, G(n, p)) is identified and the asymptotic tightness of the mean-field approximation is also established.