{
  "id": "1011.3342",
  "version": "v2",
  "published": "2010-11-15T11:10:22.000Z",
  "updated": "2017-07-07T21:03:30.000Z",
  "title": "Intersecting Families of Permutations",
  "authors": [
    "David Ellis",
    "Ehud Friedgut",
    "Haran Pilpel"
  ],
  "comment": "'Erratum' section added. Yuval Filmus has recently pointed out that the 'Generalised Birkhoff theorem', Theorem 29, is false for k > 1, and so is Theorem 27 for k > 1. An alternative proof of the equality part of the Deza-Frankl conjecture is referenced, bypassing the need for Theorems 27 and 29",
  "categories": [
    "math.CO",
    "math.RT"
  ],
  "abstract": "A set of permutations $I \\subset S_n$ is said to be {\\em k-intersecting} if any two permutations in $I$ agree on at least $k$ points. We show that for any $k \\in \\mathbb{N}$, if $n$ is sufficiently large depending on $k$, then the largest $k$-intersecting subsets of $S_n$ are cosets of stabilizers of $k$ points, proving a conjecture of Deza and Frankl. We also prove a similar result concerning $k$-cross-intersecting subsets. Our proofs are based on eigenvalue techniques and the representation theory of the symmetric group.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-11-15T11:10:22.000Z",
      "comment": "An expanded version (with slightly more detail and an added open problems section added) of a paper written in late 2008, previously available from the authors' webpages",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2017-07-07T21:03:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E10",
      "20C30",
      "05D99"
    ],
    "keywords": [
      "intersecting families",
      "permutations",
      "eigenvalue techniques",
      "representation theory",
      "symmetric group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1011.3342E"
    }
  }
}