A family of permutations $mathcal{F} subset S_{n}$ is said to be $t$-intersecting if any two permutations in $mathcal{F}$ agree on at least $t$ points. It is said to be $(t-1)$-intersection-free if no two permutations in $mathcal{F}$ agree on exactly $t-1$ points. If $S,T subset {1,2,ldots,n}$ with $|S|=|T|$, and $pi: S to T$ is a bijection, the $pi$-star in $S_n$ is the family of all permutations in $S_n$ that agree with $pi$ on all of $S$. An $s$-star is a $pi$-star such that $pi$ is a bijection between sets of size $s$. Friedgut and Pilpel, and independently the first author, showed that if $mathcal{F} subset S_n$ is $t$-intersecting, and $n$ is sufficiently large depending on $t$, then $|mathcal{F}| leq (n-t)!$; this proved a conjecture of Deza and Frankl from 1977. Equality holds only if $mathcal{F}$ is a $t$-star. In this paper, we give a more `robust proof of a strengthening of the Deza-Frankl conjecture, namely that if $n$ is sufficiently large depending on $t$, and $mathcal{F} subset S_n$ is $(t-1)$-intersection-free, then $|mathcal{F} leq (n-t)!$, with equality only if $mathcal{F}$ is a $t$-star. The main ingredient of our proof is a `junta approximation result, namely, that any $(t-1)$-intersection-free family of permutations is essentially contained in a $t$-intersecting {em junta} (a `junta being a union of a bounded number of $O(1)$-stars). The proof of our junta approximation result relies, in turn, on a weak regularity lemma for families of permutations, a combinatorial argument that `bootstraps a weak notion of pseudorandomness into a stronger one, and finally a spectral argument for pairs of highly-pseudorandom fractional families. Our proof employs four different notions of pseudorandomness, three being combinatorial in nature, and one being algebraic.
Download