“Cross-intersecting families of permutations and the Cameron-Ku conjecture"

We call a family of permutations A in Sn 'intersecting' if any two permutations in A agree in at least one position. Deza and Frankl observed that an intersecting family of permutations has size at most (n-1)!; Cameron and Ku proved that equality is attained only by families of the form {σ in Sn: σ(i)=j} for i, j in [n].

We will sketch a proof of the following `stability' result: an intersecting family of permutations which has size at least (1-1/e + o(1))(n-1)! must be contained in {σ in Sn: σ(i)=j} for some i,j in [n]. This proves a conjecture of Cameron and Ku.

In order to tackle this we first use some representation theory and an eigenvalue argument to prove a conjecture of Leader concerning cross-intersecting families of permutations: if n >= 4 and A,B is a pair of cross-intersecting families in Sn, then |A||B|