Speaker: Noam Lifshitz (HUJI)

Title: Forbidden intersections for permutations

Abstract: In 1977 Deza and Frankl posed the problem: Given $t$, how large can a set $A$ of permutations in $S_n$ be given that each two permutations in $A$ agree on at least $t$ elements? 

Such sets are called $t$ intersecting. They conjectured that the obvious $t$ intersecting example of size (n-t)! is in fact the largest one, provided that n>n_0(t). The Deza-Frankl conjecture was settled independently by Ellis, and Friedgut—Pilpel in 2011. Their beautiful  proof combines representation theory of the symmetric group and an SDP approach. 

We give a new proof of the Deza Frankl conjecture that’s based on the so called `junta method’. Our method additionally yields the following: 

Stability:We were able to determine the structure of any t-intersecting set of size n!/poly(n). 

Generality: Our proof works for a wider class than the class of $t$-intersecting sets. It also works for the class of $(t-1)$ avoiding sets, where the SDP approach is known to fail miserably for t>2. Here a set $A$ of permutations is called $t$-avoiding if no two permutations in $A$ agree on exactly $t$ elements. 

Our approach involves two main ingredients:

(1) A combinatorial one, which reduces the original problem to a Similar problem about `pseudorandom‘ sets of permutations.

(2) A representation theoretic argument, which shows that `pseudorandom’ sets of permutations cannot be t-intersecting. 

Based on a joint work with David Ellis.