Abstract
Fifty years ago Erdos 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 nl-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 n2.In this paper we solve Erdos' problem for (k, l) = (3, 4) and (k, l) = (4, 3). Using stability arguments we also characterize the precise structure of extremal examples, confirming Erdos' conjecture for (k, l) = (3, 4) and showing that a blow-up of a 5-cycle gives the minimum for (k, l) = (4, 3).
Original language | English (US) |
---|---|
Pages (from-to) | 344-373 |
Number of pages | 30 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 103 |
Issue number | 3 |
DOIs | |
State | Published - May 2013 |
Bibliographical note
Funding Information:E-mail addresses: [email protected] (S. Das), [email protected] (H. Huang), [email protected] (J. Ma), [email protected] (H. Naves), [email protected] (B. Sudakov). 1 Research supported by a UC Dissertation Year Fellowship. 2 Research supported in part by NSF grant DMS-1101185, by AFOSR MURI grant FA9550-10-1-0569 and by a USA–Israeli BSF grant.
Keywords
- Clique density
- Erdos' conjecture
- Flag algebras