July 2021 Spectral edge in sparse random graphs: Upper and lower tail large deviations
Bhaswar B. Bhattacharya, Sohom Bhattacharya, Shirshendu Ganguly
Author Affiliations +
Ann. Probab. 49(4): 1847-1885 (July 2021). DOI: 10.1214/20-AOP1495

Abstract

In this paper, we consider the problem of estimating the joint upper and lower tail large deviations of the edge eigenvalues of an Erdős–Rényi random graph Gn,p, in the regime of p where the edge of the spectrum is no longer governed by global observables, such as the number of edges, but rather by localized statistics, such as high degree vertices. Going beyond the recent developments in mean-field approximations of related problems, this paper provides a comprehensive treatment of the large deviations of the spectral edge in this entire regime, which notably includes the well-studied case of constant average degree. In particular, for r1 fixed, we pin down the asymptotic probability that the top r eigenvalues are jointly greater/less than their typical values by multiplicative factors bigger/smaller than 1, in the regime mentioned above. The proof for the upper tail relies on a novel structure theorem, obtained by building on estimates in (Combin. Probab. Comput. 12 (2003) 61–72), followed by an iterative cycle removal process, which shows, conditional on the upper tail large deviation event, with high probability the graph admits a decomposition in to a disjoint union of stars and a spectrally negligible part. On the other hand, the key ingredient in the proof of the lower tail is a Ramsey-type result which shows that if the Kth largest degree of a graph is not atypically small (for some large K depending on r), then either the top eigenvalue or the rth largest eigenvalue is larger than that allowed by the lower tail event on the top r eigenvalues, thus forcing a contradiction. The above arguments reduce the problems to developing a large deviation theory for the extremal degrees which could be of independent interest.

Citation

Download Citation

Bhaswar B. Bhattacharya. Sohom Bhattacharya. Shirshendu Ganguly. "Spectral edge in sparse random graphs: Upper and lower tail large deviations." Ann. Probab. 49 (4) 1847 - 1885, July 2021. https://doi.org/10.1214/20-AOP1495

Information

Received: 1 April 2020; Revised: 1 November 2020; Published: July 2021
First available in Project Euclid: 13 May 2021

Digital Object Identifier: 10.1214/20-AOP1495

Subjects:
Primary: 05C80 , 15A18‎ , 60B20 , 60F10

Keywords: Erdős–Rényi random graph , Extreme eigenvalues , large deviations , random matrices

Rights: Copyright © 2021 Institute of Mathematical Statistics

Vol.49 • No. 4 • July 2021
Back to Top