{
  "id": "1311.4147",
  "version": "v2",
  "published": "2013-11-17T11:25:23.000Z",
  "updated": "2014-01-09T01:19:52.000Z",
  "title": "Maximizing the number of independent sets of a fixed size",
  "authors": [
    "Wenying Gan",
    "Po-Shen Loh",
    "Benny Sudakov"
  ],
  "comment": "5 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$. Engbers and Galvin asked how large $i_t(G)$ could be in graphs with minimum degree at least $\\delta$. They further conjectured that when $n\\geq 2\\delta$ and $t\\geq 3$, $i_t(G)$ is maximized by the complete bipartite graph $K_{\\delta, n-\\delta}$. This conjecture has drawn the attention of many researchers recently. In this short note, we prove this conjecture.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-01-09T01:19:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "independent sets",
      "fixed size",
      "conjecture",
      "complete bipartite graph",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1311.4147G"
    }
  }
}