On the upper tail of star counts in random graphs (Q6966480)

The authors investigate precise asymptotics of the ``upper tail problem'' for star counts in binomial random graphs, focusing in the sparser regimes where such results were previously unknown. More precisely, the authors consider \(X = X_{n, p, r}\) as the random variable that counts the number of stars with \(r\) leaves in a binomial random graph \(G(n,p)\), and \(\mu\) is the expected value of \(X\). The ``upper tail problem'' consists on obtaining the asymptotics, as \(n\) tends to infinity, of\N\[\N- \log \Pr[ X \geq (1 + \varepsilon) \mu ].\N\]\NThis upper tail has different behaviours depending on the graph being counted, and the values of \(p\) (and consequently \(\mu\)). Previous results on the study of upper tails was given by the breakthrough results of \textit{M. Harel} et al. [Duke Math. J. 171, No. 10, 2089--2192 (2022; Zbl 1500.60002)] who (as consequence of much more general results) find the asymptotics of the upper tail problem for stars in the regime \(1 \ll \mu \ll (\log n)^{r/(r-1)}\); this is the ``Poisson regime'', where the random variable \(X\) is expected to behave similarly to a Poisson random variable. Another relevant result by \textit{N. A. Cook} et al. [Duke Math. J. 173, No. 5, 873--946 (2024; Zbl 1540.05129)] covers the range \(n^{-1/r} \ll p \ll 1\); this is the ``localization regime'', where large deviations occur mainly to the appearance of small and simple structures. The authors then solve the remaining case, which is for \(\mu = \Omega((\log n)^{r/(r-1)})\) and \(\mu = O(n^r)\). The main result here is Theorem 1.1, which gives a precise formula (see (1.7)) for the asymptotics of \(- \log \Pr[ X \geq (1 + \varepsilon) \mu ]\) in all ranges between the Poisson regime and the localization regime.\N\NThe proof proceeds by treating the number of stars in a binomial random graph as a function of the degree sequence of the random graph, which allows the use of the asymptotic enumeration formulas by \textit{B. D. McKay} [Ars Comb. 19A, 15--25 (1985; Zbl 0568.05032)] for graphs with a given degree sequence; this is further reduced to the study of a sum of i.i.d. random variables instead of the degree sequence. This approach works for the sparser values of \(p\). For larger values of \(p\) (closer to the ``localization regime''), the authors can work by directly analysing the degrees of the binomial random graph using concentration inequalities, refining the approach of \textit{M. Šileikis} and \textit{L. Warnke} [Electron. J. Comb. 27, No. 1, Research Paper P1.67, 23 p. (2020; Zbl 1435.05183)].