On the Upper Tail of Counts of Strictly Balanced Subgraphs

Let XG be the number of copies of G in the Erdős-Rényi binomial random graph G(n,p). Janson, Oleszkiewicz and Ruciński proved that for every $t > 1${equation*}exp \{-O_t( M^*_G ln (1/p))\} ≤ P\{X_G ≥ t\,E X_G\} ≤ exp\{-Ω_t(M^*_G)\},{equation*}where M^*G is a certain function of n and p. For G = K₃ the logarithmic gap between the bounds was closed by Chatterjee and, independently, DeMarco and Kahn. We provide matching bounds for strictly balanced G, when E XG ≤ ln n. Also, we give matching bounds for C₄, K₄, and stars K1,k in a broader range of E XG. In particular, this improves some results of Janson and Ruciński for which the so called deletion method was used.