An Eventown Result for Permutations

Abstract

A family of permutations $\mathcal{F}\subseteq S_n$ is even-cycle-intersecting if $\ddot{I}ƒ\ddot{I}{€}^{-1}$ has an even cycle for all $\ddot{I}ƒ,\ddot{I}€\in \mathcal{F}$. We show that if $\mathcal{F}\subseteq S_n$ is an even-cycle-intersecting family of permutations, then $|\mathcal{F}|\le 2^{n-1}$, and that equality holds when $n$ is a power of 2 and $\mathcal{F}$ is a double-translate of a Sylow 2-subgroup of $S_n$. This result can be seen as an analogue of the classical eventown problem for subsets and it confirms a conjecture of János Körner on maximum reversing families of the symmetric group. Along the way, we show that the canonically intersecting families of $S_n$ are also the extremal odd-cycle-intersecting families of $S_n$ for all even $n$. While the latter result has less combinatorial significance, its proof uses an interesting new character-theoretic identity that might be of independent interest in algebraic combinatorics.