Supersaturation for hereditary properties

Abstract

Let $\mathcal{F}$ be a collection of $r$-uniform hypergraphs, and let $0<p<1$. It is known that there exists $c=c(p,\mathcal{F})$ such that the probability of a random $r$-graph in $G(n,p)$ not containing an induced subgraph from $\mathcal{F}$ is $2^{(-c+o(1))\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$. Let each graph in $\mathcal{F}$ have at least $t$ vertices. We show that in fact for every $\hat{I}\mu >0$, there exists $\hat{I}´=\hat{I}´(\hat{I}\mu ,p,\mathcal{F})>0$ such that the probability of a random $r$-graph in $G(n,p)$ containing less than $\hat{I}´n^t$ induced subgraphs each lying in $\mathcal{F}$ is at most $2^{(-c+\hat{I}\mu )\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$. This statement is an analogue for hereditary properties of the supersaturation theorem of Erdős and Simonovits. In our applications we answer a question of Bollobás and Nikiforov.

5 pages, submitted to European Journal of Combinatorics