Upper Tail Bounds for Stars - Šileikis, Matas; Warnke, Lutz (The Electronic Journal of Combinatorics, 2020)
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+ε){\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 Janson and Ruciński, and confirms a conjecture by DeMarco and Kahn). In contrast to the widely accepted standard for the upper tail problem, we do not restrict our attention to constant $ε$, but also allow for $ε \ge n^{-α}$ deviations.