Counting cliques in graphs with small independence number

Abstract

We prove that for all fixed $k\ge 4$, any $N$ vertex graph with no independent set of size $n$ and $N\ge \hat{I}\text{c◯}(n^{k-1}/{\log }^{k-2}n)$ contains at least $$\hat{I}\text{c◯}\left(\right(\genfrac{}{}{0ex}{}{N}{k}\left)\right(\frac{\log n}{n}{)}^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}/\log n)$$ cliques of order $k$, and for $k\ge 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án'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.

13 pages