Upper tail of the spectral radius of sparse Erdös-Rényi graphs (Q6070368)

A plain way to choose a (simple) graph at random is to fix a set of \(n\) vertices and choose the edges independently with probability \(p\) (the case \(p=1/2\) amounts to an equiprobable choice of the simple graph among all with the given set of vertices). Meanwhile, a typical graph-theoretic question is whether under given hypotheses a graph enjoys a certain property or not, for random graphs one is interested in calculating the probability of that property. Such a calculation may often be too cumbersome, but the asymptotic behavior as \(n\) (and possibly \(p\)) tends to infinity is handier and useful for applications (typically to networks with a sufficiently high number of nodes, of course). For instance, quite precise and interesting results on connectedness and related properties are presented in [\textit{P. Erdős} and \textit{A. Rényi}, Bull. Inst. Int. Stat. 38, No. 4, 343--347 (1961; Zbl 0106.12006)]. That paper is cast in a different setting, where the edges are equiprobably chosen in a prescribed number \(N\) since, in their view, the growth of \(N\) models to some extent the evolution of networks over time; but it also contains a fair explanation on how results in the `\(p\)-setting' can be deduced (given at the point when the described evolution arrives at an almost surely connected graph, that is, when \(N(n)\to\infty\) sufficiently fast that the probability that the random graph is connected tends to \(1\)). The broad field pioneered by Erdős and Rényi has been widely explored in its various aspects, either concerning probability or graph theory. For instance, in [\textit{S. Chatterjee} and \textit{S. R. S. Varadhan}, Eur. J. Comb. 32, No. 7, 1000--1017 (2011; Zbl 1230.05259)] large deviations are considered. Useful information on the spectral radius, that is, the largest eigenvalue of the adjacency matrix, and on other spectral data can be borrowed from the considerable amount of works, more generally on random matrices, that are available in the literature. But inevitably only a few of them deal with atypical behaviors such as large deviations, and they are generally suitable for dense matrices, meanwhile, the adjacency matrices of Erdős--Rényi graphs at the early stages of their evolution are obviously sparse. That state of the art is reviewed in the careful introduction provided by the paper under consideration. As also explained there, more specialized investigations have been performed in very recent times, and the results of the paper almost complete the picture of the evolution of Erdős--Rényi graphs, with regard to upper tail large deviations of the spectral radius. Some more inherently graph-theoretic information is also provided, e.g., about homomorphism counts of cycles of even length into the graph. Additionally, the relationship with a mean-field variational problem similar to the one that was considered in the mentioned paper by Chatterjee and Varadhan for triangle counts is carefully analyzed and confirmed, despite lack of prior solutions to this particular problem in the literature.