{
  "id": "math/0508081",
  "version": "v1",
  "published": "2005-08-03T22:19:10.000Z",
  "updated": "2005-08-03T22:19:10.000Z",
  "title": "Eigenvalue bounds for independent sets",
  "authors": [
    "C. D. Godsil",
    "M. W. Newman"
  ],
  "comment": "18 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We derive bounds on the size of an independent set based on eigenvalues. This generalizes a result due to Delsarte and Hoffman. We use this to obtain new bounds on the independence number of the Erd\\H{o}s-R\\'{e}nyi graphs. We investigate further properties of our bounds, and show how our results on the Erd\\H{o}s-R\\'{e}nyi graphs can be extended to other polarity graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-08-03T22:19:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "51E15",
      "51E12"
    ],
    "keywords": [
      "independent set",
      "eigenvalue bounds",
      "independence number",
      "polarity graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......8081G"
    }
  }
}