Even-Intersecting Families of Permutations

Abstract

A family of permutations in $S_n$ is called even-intersecting if every two distinct members agree in an even number of positions. Let $M(n)$ denote the maximum size of such a family. For even $n$, we prove that $$n!!\le M(n)\le e^{\frac{n}{2}+o(n)}n!!,$$ improving the bound obtained from a theorem of Cameron, Deza and Frankl (1987) by an exponential factor. This problem may be viewed as a permutation analogue of the classical Eventown problem for set systems. For odd $n$, we give a construction yielding $M(n)\ge n^2/4$. We further extend this construction to obtain $$M(n)\ge (n-\sqrt{n-1}{)}^2,$$ whenever $n=(q+1{)}^2+1$ and $q$ is an odd prime power. The latter bound asymptotically matches the upper bound $M(n)\le (n-1{)}^2+1$ obtained by Cameron, Deza and Frankl.

31 pages