{
  "id": "1203.2723",
  "version": "v1",
  "published": "2012-03-13T06:53:35.000Z",
  "updated": "2012-03-13T06:53:35.000Z",
  "title": "A problem of Erdős on the minimum number of $k$-cliques",
  "authors": [
    "Shagnik Das",
    "Hao Huang",
    "Jie Ma",
    "Humberto Naves",
    "Benny Sudakov"
  ],
  "comment": "35 pages, 12 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-03-13T06:53:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "minimum number",
      "complete graphs",
      "conjecture",
      "extremal examples",
      "independence number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.2723D"
    }
  }
}