Extremal Families for Matchings in Permutations

Abstract

Two permutations $\sigma ,\tau \in S_n$ are called disjoint if the composition $\sigma {\tau }^{-1}$ has no fixed point. If a family $\mathcal{F}\subseteq S_n$ contains no $s$ pairwise disjoint permutations, then a simple averaging argument gives $|\mathcal{F}|\le (s-1)(n-1)!$. Inozemtsev, Kolupaev and Kupavskii characterized the equality cases in the range $s\le n/(2^{17}\log n).$ We characterize all equality cases throughout the range $2\le s\le n$: equality holds if and only if $\mathcal{F}$ is a union of $(s-1)$ pairwise disjoint $1$-cosets. We also prove the linear statement underlying this classification: a real-valued function on $S_n$ has constant sum on every one-factorization if and only if it lies in the span of the indicators of the $1$-cosets. The proof is combinatorial and applies to every order, with a few small orders handled separately.