A problem of Erdős on the minimum number of $k$-cliques

Shagnik Das, Hao Huang, Jie Ma, Humberto Naves, Benny Sudakov

Published 2012-03-13Version 1

Fifty years ago Erd\H{o}s asked to determine the minimum number of $k$-cliques in a graph on $n$ vertices with independence number less than l. He conjectured that this minimum is achieved by the disjoint union of $l-1$ complete graphs of size $\frac{n}{l-1}$. This conjecture was disproved by Nikiforov who showed that the balanced blow-up of a 5-cycle has fewer 4-cliques than the union of 2 complete graphs of size $\frac{n}{2}$. In this paper we solve Erd\H{o}s' problem for $(k,l)=(3,4)$ and $(k,l)=(4,3)$. Using stability arguments we also characterize the precise structure of extremal examples, confirming Erd\H{o}s' conjecture for $(k,l)=(3,4)$ and showing that a blow-up of a 5-cycle gives the minimum for $(k,l)=(4,3)$.