Upper Tail Bounds for Stars

Abstract

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+ε)EX), 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^(-a) deviations.