On the upper tail of counts of strictly balanced subgraphs (Q426748)

Summary: Let \(X_G\) be the number of copies of \(G\) in the Erdős-Rényi binomial random graph \(\mathbb G(n,p)\). \textit{S. Janson}, \textit{K. Oleszkiewicz} and \textit{A. Ruciński} [Isr. J. Math. 142, 61--92 (2004; Zbl 1055.05136)] proved that for every \(t > 1\) \[ \exp \{-O_t( M^*_G \ln (1/p))\} \leq \mathbb{P}\{X_G \geq t\,\mathbb{E} X_G\} \leq \exp\{-\Omega_t(M^*_G), \] where \(M^*_G\) is a certain function of \(n\) and \(p\). For \(G = K_3\) the logarithmic gap between the bounds was closed by \textit{S. Chatterjee} [Random Struct. Algorithms 40, No. 4, 437--451 (2012)] and, independently, \textit{B. DeMarco} and \textit{J. Kahn} [ibid. 40, No. 4, 452--459 (2012)]. We provide matching bounds for strictly balanced \(G\), when \(\mathbb{E} X_G \leq \ln n\). Also, we give matching bounds for \(C_4, K_4\), and stars \(K_{1,k}\) in a broader range of \(\mathbb{E} X_G\). In particular, this improves some results of \textit{S. Janson} and \textit{A. Ruciński} [ibid. 20, No. 3, 317--342 (2002; Zbl 0996.60023)] for which the so called deletion method was used.