{
  "id": "0807.3115",
  "version": "v3",
  "published": "2008-07-19T19:10:56.000Z",
  "updated": "2009-08-19T03:30:09.000Z",
  "title": "Stability for t-intersecting families of permutations",
  "authors": [
    "David Ellis"
  ],
  "comment": "28 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A family of permutations (\\mathcal{A} \\subset S_{n}) is said to be (t)-\\textit{intersecting} if any two permutations in (\\mathcal{A}) agree on at least (t) points, i.e. for any (\\sigma, \\pi \\in \\mathcal{A}), (|\\{i \\in [n]: \\sigma(i)=\\pi(i)\\}| \\geq t). It was recently proved by Friedgut, Pilpel and the author that for (n) sufficiently large depending on (t), a (t)-intersecting family (\\mathcal{A} \\subset S_{n}) has size at most ((n-t)!), with equality only if (\\mathcal{A}) is a coset of the stabilizer of (t) points (or `(t)-coset' for short), proving a conjecture of Deza and Frankl. Here, we first obtain a rough stability result for (t)-intersecting families of permutations, namely that for any (t \\in \\mathbb{N}) and any positive constant (c), if (\\mathcal{A} \\subset S_{n}) is a (t)-intersecting family of permutations of size at least (c(n-t)!), then there exists a (t)-coset containing all but at most a (O(1/n))-fraction of (\\mathcal{A}). We use this to prove an exact stability result: for (n) sufficiently large depending on (t), if (\\mathcal{A} \\subset S_{n}) is a (t)-intersecting family which is not contained within a (t)-coset, then (\\mathcal{A}) is at most as large as the family \\mathcal{D} & = & \\{\\sigma \\in S_{n}: \\sigma(i)=i \\forall i \\leq t, \\sigma(j)=j \\textrm{for some} j > t+1\\} && \\cup \\{(1 t+1),(2 t+1),...,(t t+1)\\} which has size ((1-1/e+o(1))(n-t)!). Moreover, if (\\mathcal{A}) is the same size as (\\mathcal{D}) then it must be a `double translate' of (\\mathcal{D}), meaning that there exist (\\pi,\\tau \\in S_{n}) such that (\\mathcal{A}=\\pi \\mathcal{D} \\tau). We also obtain an analogous result for (t)-intersecting families in the alternating group (A_{n}).",
  "revisions": [
    {
      "version": "v3",
      "updated": "2009-08-19T03:30:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "permutations",
      "t-intersecting families",
      "sufficiently large depending",
      "exact stability result",
      "rough stability result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0807.3115E"
    }
  }
}