{
  "id": "1604.06135",
  "version": "v1",
  "published": "2016-04-20T22:42:26.000Z",
  "updated": "2016-04-20T22:42:26.000Z",
  "title": "A tight stability version of the Complete Intersection Theorem",
  "authors": [
    "Nathan Keller",
    "Noam Lifshitz"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "A set family F is said to be t-intersecting if any two sets in F share at least t elements. The Complete Intersection Theorem of Ahlswede and Khachatrian (1997) determines the maximal size f(n,k,t) of a t-intersecting family of k-element subsets of {1,2,...,n}, and gives a full characterisation of the extremal families. In this paper, we prove the following `stability version' of the theorem: if k/n is bounded away from 0 and 1/2, and F is a t-intersecting family of k-element subsets of {1,2,...,n} such that $|F| \\geq f(n,k,t) - O \\binom{n-d}{k}$, then there exists an extremal family G such that $|F \\setminus G| = O \\binom{n-d}{k-d}$. For fixed t, this assertion is tight up to a constant factor. This proves a conjecture of Friedgut from 2008. Our proof combines classical shifting arguments with a `bootstrapping' method based upon an isoperimetric argument.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-04-20T22:42:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05D40"
    ],
    "keywords": [
      "complete intersection theorem",
      "tight stability version",
      "k-element subsets",
      "isoperimetric argument",
      "constant factor"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160406135K"
    }
  }
}