Upper Tail Bounds for Stars

Source abstract

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+\epsilon){\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 $\epsilon$, but also allow for $\epsilon \ge n^{-\alpha}$ deviations.