Supersaturation for hereditary properties

Let FF be a collection of rr-uniform hypergraphs, and let 00ϵ>0, there exists δ=δ(ϵ,p,F)>0δ=δ(ϵ,p,F)>0 such that the probability of a random rr-graph in G(n,p)G(n,p) containing fewer than δntδnt induced subgraphs each lying in FF is at most 2(−c+ϵ)nr.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.

► We prove a supersaturation-type result for hereditary properties of graphs. ► The number of graphs without a fixed induced subgraph is approximately the same as the number of graphs without a positive density of induced subgraphs. ► Our result generalizes to hypergraphs and collections of forbidden induced subgraphs. ► Our result generalizes to counting with an edge-probability measure. ► Our proofs avoid Szemeredi’s Regularity Lemma.