Counting cliques in graphs with small independence number

Abstract

We prove that for all fixed $k\geq 4$, any $N$ vertex graph with no independent set of size $n$ and $N\geq \Omega(n^{k-1}/\log^{k-2}n)$ contains at least $$ \Omega\bigg(\binom Nk \Big(\frac{\log n}{n}\Big)^{\binom k2}/\log n\bigg) $$ cliques of order $k$, and for $k\geq 5$ this is best possible conditional on the known upper bounds for $r(k,n)$. This is also true and tight for $k=2$ by Tur\'an's Theorem and for $k=3$ by a result of Bohman and Mubayi. We show the bound is also tight for $k=4$. We obtain other supersaturation results using the same methods.