Upper tail bounds for stars (Q2309238)

Summary: For \(r\ge 2\), let \(X\) be the number of \(r\)-armed stars \(K_{1,r}\) in the binomial random graph \(G_{n,p}\). We study the upper tail \(\mathbb{P}(X \ge (1+\varepsilon)\mathbb{E}X)\), and establish exponential bounds which are best possible up to constant factors in the exponent (for the special case of stars \(K_{1,r}\) this solves a problem of \textit{S. Janson} and \textit{A. Ruciński} [Ark. Mat. 49, No. 1, 79--96 (2011; Zbl 1223.05201)], and confirms a conjecture by \textit{B. DeMarco} and \textit{J. Kahn} [Random Struct. Algorithms 40, No. 4, 452--459 (2012; Zbl 1246.05142)]). In contrast to the widely accepted standard for the upper tail problem, we do not restrict our attention to constant \(\varepsilon \), but also allow for \(\varepsilon \ge n^{-\alpha}\) deviations.