{
  "id": "1408.1288",
  "version": "v2",
  "published": "2014-08-06T14:18:23.000Z",
  "updated": "2016-09-06T19:04:34.000Z",
  "title": "On the stability of the Erdős-Ko-Rado theorem",
  "authors": [
    "Béla Bollobás",
    "Bhargav Narayanan",
    "Andrei Raigorodskii"
  ],
  "comment": "17 pages, fixed misprints, Journal of Combinatorial Theory, Series A",
  "categories": [
    "math.CO"
  ],
  "abstract": "Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as a uniform intersecting family, this gives us a random analogue of the Erd\\H{o}s-Ko-Rado theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-06T14:18:23.000Z",
      "abstract": "Delete the edges of a Kneser graph with some probability p, independently of each other: for what probabilities p is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erd\\H{o}s-Ko-Rado theorem.",
      "comment": "16 pages, submitted",
      "journal": null,
      "doi": null,
      "authors": [
        "Béla Bollobás",
        "Bhargav P. Narayanan",
        "Andrei M. Raigorodskii"
      ]
    },
    {
      "version": "v2",
      "updated": "2016-09-06T19:04:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05C80",
      "05D40"
    ],
    "keywords": [
      "erdős-ko-rado theorem",
      "kneser graph",
      "independence number",
      "random graph equal",
      "sharp threshold result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.1288B"
    }
  }
}