On $t$-Intersecting Families of Permutations

Abstract

We prove that there exists a constant $c_0$ such that for any $t\in \mathbb{N}$ and any $n\ge c_{0}t$, if $A\subset S_n$ is a $t$-intersecting family of permutations then$|A|\le (n-t)!$. Furthermore, if $|A|\ge 0.75(n-t)!$ then there exist $i_1,\dots ,i_t$ and $j_1,\dots ,j_t$ such that $\sigma (i_1)=j_1,\dots ,\sigma (i_t)=j_t$ holds for any $\sigma \in A$. This shows that the conjectures of Deza and Frankl (1977) and of Cameron (1988) on $t$-intersecting families of permutations hold for all $t\le c_{0}n$. Our proof method, based on hypercontractivity for global functions, does not use the specific structure of permutations, and applies in general to $t$-intersecting sub-families of `pseudorandom' families in $\{1,2,\dots ,n{\}}^n$, like $S_n$.