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.