Independence Number of Graphs with a Prescribed Number of Cliques

Abstract

We consider the following problem posed by Erdős in 1962. Suppose that $G$ is an $n$-vertex graph where the number of $s$-cliques in $G$ is $t$. How small can the independence number of $G$ be? Our main result suggests that for fixed $s$, the smallest possible independence number undergoes a transition at $t=n^{s/2+o(1)}$.

In the case of triangles ($s=3$) our method yields the following result which is sharp apart from constant factors and generalizes basic results in Ramsey theory: there exists $c>0$ such that every $n$-vertex graph with $t$ triangles has independence number at least $$c \cdot \min\left\{ \sqrt {n \log n}\, , \, \frac{n}{t^{1/3}} \left(\log \frac{n}{ t^{1/3}}\right)^{2/3} \right\}.$$