Independence Number of Graphs with a Prescribed Number of Cliques
Independence Number of Graphs with a Prescribed Number of Cliques
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 …