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

Fifty years ago Erdő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 . 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 .In this paper we solve Erdő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ő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).