Fall 2013

Families of Permutations with Forbidden Intersection-sizes

Monday, Dec. 2, 2013 3:00 pm3:45 pm PST

Add to Calendar

If A is a family of permutations of {1,2,...,n}, we say that A is t-intersecting if any two permutations in A agree on at least t distinct points. Deza and Frankl conjectured that for any integer t, a t-intersecting family of permutations of {1,2,...,n} has size at most (n-t)!, if n is sufficiently large depending on t. This was proved independently by the author and by Friedgut and Pilpel in 2008, using non-Abelian Fourier analysis, i.e. the representation theory of the symmetric group.

We make a stronger conjecture, namely that if n is sufficiently large depending on t, any family of permutations of {1,2,...,n} in which no two permutations agree on exactly t-1 points, has size at most (n-t)!. (This is analogous to Erdos' conjecture on families of r-sets with a forbidden intersection-size, proved by Frankl and Furedi in 1985.) We are able to prove this for t=2; interestingly, our  representation-theoretic techniques fail to prove the conjecture for t>2.

We will also discuss some stability results, characterising the 'large' t-intersecting families in S_{n}, and several other open problems, including a Frankl-type conjecture on the maximum-sized t-intersecting families of permutations of {1,2,...,n} for *all* pairs (n,t).