  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 \Pr(X \ge (1+\epsilon)\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 Rucinski, 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.
