A problem of Erdos on the minimum number of k-cliques

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

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

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 languageEnglish (US)
Pages (from-to)344-373
Number of pages30
JournalJournal of Combinatorial Theory. Series B
Volume103
Issue number3
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'A problem of Erdos on the minimum number of k-cliques'. Together they form a unique fingerprint.

Cite this