Independence number of graphs with a prescribed number of cliques (Q2415089)

Summary: We consider the following problem posed by \textit{P. Erdős} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459--464 (1962; Zbl 0116.01202)]. 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\}.\]