2020/04/01 by Bhaswar B. Bhattacharya, Bhattacharya, Bhaswar B., Sohom Bhattacharya +3 · 1 citation
Economics, Econometrics and Finance · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Approximation and Integration #Mathematical Physics (math-ph) #Probability (math.PR) #Statistical Methods and Inference #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.2004.00611
openalex publication_date 2020/04/01 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In this paper we consider the problem of estimating the joint upper and lower\ntail large deviations of the edge eigenvalues of an Erd Hos-R 'enyi random\ngraph \Gn,p, in the regime of p where the edge of the spectrum\nis no longer governed by global observables, such as the number of edges, but\nrather by localized statistics, such as high degree vertices. Going beyond the\nrecent developments in mean-field approximations of related problems, this\npaper provides a comprehensive treatment of the large deviations of the\nspectral edge in this entire regime, which notably includes the well studied\ncase of constant average degree. In particular, for r \≥ 1 fixed, we pin\ndown the asymptotic probability that the top r eigenvalues are jointly\ngreater/less than their typical values by multiplicative factors bigger/smaller\nthan 1, in the regime mentioned above. The proof for the upper tail relies on\na novel structure theorem, obtained by building on estimates of Krivelevich and\nSudakov (2003), followed by an iterative cycle removal process, which shows,\nconditional on the upper tail large deviation event, with high probability the\ngraph admits a decomposition in to a disjoint union of stars and a spectrally\nnegligible part. On the other hand, the key ingredient in the proof of the\nlower tail is a Ramsey-type result which shows that if the K-th largest\ndegree of a graph is not atypically small (for some large K depending on\nr), then either the top eigenvalue or the r-th largest eigenvalue is larger\nthan that allowed by the lower tail event on the top r eigenvalues, thus\nforcing a contradiction. The above arguments reduce the problems to developing\na large deviation theory for the extremal degrees which could be of independent\ninterest.\n