{
  "id": "1801.01091",
  "version": "v1",
  "published": "2018-01-03T17:41:12.000Z",
  "updated": "2018-01-03T17:41:12.000Z",
  "title": "Independence number of graphs with a prescribed number of cliques",
  "authors": [
    "Tom Bohman",
    "Dhruv Mubayi"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the following problem posed by Erdos in 1962. Suppose that $G$ is an $n$-vertex graph where the number of $s$-cliques in $G$ is $t$. How small can the independence number of $G$ be? Our main result suggests that for fixed $s$, the smallest possible independence number undergoes a transition at $t=n^{s/2+o(1)}$. In the case of triangles ($s=3$) we obtain the following result which is sharp apart from constant factors and generalizes basic results in Ramsey theory: there exists $c>0$ such that every $n$-vertex graph with $t$ triangles has independence number at least $$c \\cdot \\min\\left\\{ \\sqrt {n \\log n}\\, , \\, \\frac{n}{t^{1/3}} \\left(\\log \\frac{n}{ t^{1/3}}\\right)^{2/3} \\right\\}.$$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-03T17:41:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "prescribed number",
      "vertex graph",
      "independence number undergoes",
      "generalizes basic results",
      "main result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}