Upper Tail Bounds for Stars - Šileikis, Matas; Warnke, Lutz (The Electronic Journal of Combinatorics, 2020)
For r 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 P(X (1+ε)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 ε n^-α deviations.