On the Upper Tail of Counts of Strictly Balanced Subgraphs

[摘要] Let $X_G$ be the number of copies of $G$ in the Erdős-Rényi binomial random graph $\mathbb G(n,p)$. Janson, Oleszkiewicz and Ruciński proved that for every $t > 1$\begin{equation*}\exp \{-O_t( M^*_G \ln (1/p))\} \leq \mathbb{P}\{X_G \geq t\,\mathbb{E}

[学科分类] 离散数学和组合数学