David Ellis, Ehud Friedgut, Haran Pilpel
Published 2010-11-15, updated 2017-07-07Version 2
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.
Comments: '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
Intersecting families of sets and permutations: a survey
A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
Almost $t$-intersecting families for vector spaces
![QR code for arXiv:1011.3342 [math.CO]](http://oss.arxitics.com/images/favicon.svg)