Independence number of graphs with a prescribed number of cliques

Tom Bohman, Dhruv Mubayi

Published 2018-01-03Version 1

We consider the following problem posed by Erdos 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$) we obtain 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\}.$$