Extremal Families for Matchings in Permutations
Abstract
Two permutations σ,τ∈ Sn are called disjoint if the composition στ−1 has no fixed point. If a family ℱ⊆ Sn contains no s pairwise disjoint permutations, then a simple averaging argument gives |ℱ|≤(s−1)(n−1)!. Inozemtsev, Kolupaev and Kupavskii characterized the equality cases in the range s≤ n/(217log n). We characterize all equality cases throughout the range 2≤ s≤ n: equality holds if and only if ℱ is a union of (s−1) pairwise disjoint $1$-cosets. We also prove the linear statement underlying this classification: a real-valued function on Sn 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.
Related
- Minimum blockers and extremal graphs for nonnested matchings
- Extremal permutations of ℤn with many good slopes and applications to quantum Latin squares
- Even-Intersecting Families of Permutations
- The maximum t-diversity of t-intersecting families of permutations
- Sharp stability for cross t-intersecting families of permutations in the linear range
BibTeX
@misc{cao2026extremal,
title = {{Extremal Families for Matchings in Permutations}},
author = {Mengyu Cao and Haixiang Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03904},
eprint = {2609.03904},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03904},
}
RIS
TY - UNPB
TI - Extremal Families for Matchings in Permutations
AU - Mengyu Cao
AU - Haixiang Zhang
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03904
UR - https://arxiv.org/abs/2609.03904
AB - Two permutations σ,τ∈ S_n are called disjoint if the composition στ^−1 has no fixed point. If a family ℱ⊆ S_n contains no s pairwise disjoint permutations, then a simple averaging argument gives |ℱ|≤(s−1)(n−1)!. Inozemtsev, Kolupaev and Kupavskii characterized the equality cases in the range s≤ n/(2^17log n). We characterize all equality cases throughout the range 2≤ s≤ n: equality holds if and only if ℱ 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.
ER -