The Kézdy–Snevily conjecture: $f(n,2)=n$ for even $n$ and $f(n,2)>n$ for odd $n$ (covering radius of sets of permutations in the Hamming permutation space)

Let $f(n,s)$ denote the minimum size of a set $S$ of permutations of $\{1,\dots,n\}$ such that every permutation agrees with some member of $S$ in at least $s$ positions (Hamming distance at most $n-s$). Kézdy and Snevily conjectured that $f(n,2)=n$ for even $n$ and $f(n,2)>n$ for odd $n$; the conjecture implies the long-standing Ryser and Brualdi–Ryser–Stein conjectures on transversals of Latin squares. Hendrey and Wanless (2020) proved that the odd case implies the whole conjecture and that $f(n,2)>3n/4$. No later resolution is known, and the implied transversal conjectures remain open, so the conjecture — equivalently, the odd case $f(n,2)>n$ — survives as a precise open problem.

Background

Let $\mathcal{S}_n$ be the set of all permutations of $\{1,\dots,n\}$, viewed as words of length $n$ over an alphabet of $n$ symbols. The Hamming distance $d(\rho,\sigma)$ between two permutations is the number of positions in which they differ. For a set $S\subseteq\mathcal{S}_n$, its covering radius $\mathrm{cr}(S)$ is $\max_{\rho\in\mathcal{S}_n}\min_{\sigma\in S} d(\rho,\sigma)$, the worst-case distance from an arbitrary permutation to the nearest member of $S$; a small $S$ with small covering radius is a covering code for permutation space. Following Cameron and Wanless (2005), define $f(n,s)$ as the minimum size of a set $S\subseteq\mathcal{S}_n$ with $\mathrm{cr}(S)\le n-s$, i.e. the fewest permutations needed so that every permutation agrees with at least one of them in at least $s$ positions. Equivalently, $f(n,s)$ is the smallest number of perfect matchings of the complete bipartite graph $K_{n,n}$ such that every perfect matching shares at least $s$ edges with one of them, a formulation used heavily in the strongest known bounds.

The case $s=2$ connects to the theory of Latin squares. A Latin square of order $n$ is an $n\times n$ array filled with $n$ symbols so that each symbol appears once in every row and column; its rows, read as functions from columns to symbols, form a set of $n$ permutations. A transversal is a selection of $n$ cells sharing no row, column, or symbol, and a near transversal has $n-1$ such cells. Two famous open conjectures concern these objects: Ryser's conjecture asserts that every Latin square of odd order has a transversal, and the Brualdi–Ryser–Stein conjecture asserts that every Latin square has a near transversal (see Wanless's 2011 survey). Cameron and Wanless (2005) showed that the rows of a Latin square with no transversal have covering radius exactly $n-2$, and they recorded a conjecture of Kézdy and Snevily: $f(n,2)=n$ for even $n$ and $f(n,2)>n$ for odd $n$. This conjecture is stronger than both transversal conjectures above: proving it would settle Ryser's conjecture and the Brualdi–Ryser–Stein conjecture. Cameron and Wanless proved $\lfloor n/2\rfloor+2\le f(n,2)\le 4n/3+O(1)$; later, Cavenagh and Wanless (2017) constructed Latin squares without transversals of every even order, whose rows give $f(n,2)\le n$ for even $n$. A set of permutations is called transitive if for every pair of positions $x,y$ some member of the set maps $x$ to $y$; any transitive subset of $\mathcal{S}_n$ has at least $n$ elements, since each member maps a fixed $x$ to a single image, and this elementary obstruction underlies the conjecture's parity dichotomy.

Wanless and Zhang (2013) improved the upper bounds to $f(n,2)\le n+O(\log n)$ for all $n$ and $f(n,2)\le n+2$ whenever $3\mid n$. Hendrey and Wanless (2020) then proved, via a reduction showing that a failure of the even case would force a failure of the preceding odd case, that the odd case $f(n,2)>n$ implies the entire conjecture; they also improved the lower bound to $f(n,2)>3n/4$ for all $n$ using a rainbow-matching argument in $K_{n,n}$ (a rainbow matching is one whose edges carry pairwise distinct colours, where each permutation colours the edges of one perfect matching). For general $s\ge 3$ they proved $s!<f(n,s)<3s!(n-s)\log n$ and a linear-in-$n$ lower bound, in particular $f(n,3)>n$. Nothing is known to close the gap between the lower bound $f(n,2)>3n/4$ and the conjectured values: for even $n$ the remaining task is the lower bound $f(n,2)\ge n$ (the upper bound $f(n,2)\le n$ is known), and for odd $n$ it is the lower bound $f(n,2)>n$ (where the best upper bound is $n+O(\log n)$). The conjecture remains open.

Problem Statement

Prove or disprove the Kézdy–Snevily conjecture: for every even positive integer $n$, $f(n,2)=n$, and for every odd positive integer $n$, $f(n,2)>n$, where $f(n,2)$ is the minimum size of a set $S\subseteq\mathcal{S}_n$ of permutations of $\{1,\dots,n\}$ such that every permutation of $\{1,\dots,n\}$ is within Hamming distance $n-2$ of at least one member of $S$. By Corollary 2 of Hendrey and Wanless (2020), it suffices to prove the strict inequality $f(n,2)>n$ for odd $n$: that single statement implies the conjecture for all $n$, and in turn Ryser's transversal conjecture and the Brualdi–Ryser–Stein near-transversal conjecture. Equivalently, the conjecture is the exact determination of $f(n,2)$ as a function of $n$, namely the parity dichotomy $f(n,2)=n$ for every even $n$ and $f(n,2)>n$ for every odd $n$.

References

1. Kevin Hendrey, Ian M. Wanless, Covering radius in the Hamming permutation space, European Journal of Combinatorics 84 (2020) 103025. DOI: 10.1016/j.ejc.2019.103025, https://doi.org/10.1016/j.ejc.2019.103025 (preprint arXiv:1811.09040, https://arxiv.org/abs/1811.09040)
2. Peter J. Cameron, Ian M. Wanless, Covering radius for sets of permutations, Discrete Mathematics 293 (2005) 91–109. DOI: 10.1016/j.disc.2004.08.024, https://doi.org/10.1016/j.disc.2004.08.024
3. Ian M. Wanless, Xiande Zhang, Transversals of Latin squares and covering radius of sets of permutations, European Journal of Combinatorics 34 (2013) 1130–1143. DOI: 10.1016/j.ejc.2013.04.001, https://doi.org/10.1016/j.ejc.2013.04.001
4. Nicholas J. Cavenagh, Ian M. Wanless, Latin squares with no transversals, Electronic Journal of Combinatorics 24(2) (2017) #P2.45. DOI: 10.37236/6481, https://doi.org/10.37236/6481
5. Ian M. Wanless, Transversals in Latin squares: a survey, in Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series 392, Cambridge University Press (2011) 403–437. DOI: 10.1017/cbo9781139004114.010, https://doi.org/10.1017/cbo9781139004114.010
6. Luis Goddyn, Kevin Halasz, All group-based Latin squares possess near transversals, Journal of Combinatorial Designs 28 (2020) 358–365. DOI: 10.1002/jcd.21701, https://doi.org/10.1002/jcd.21701
7. Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery, Teo Petrov, Almost-full transversals in equi-$n$-squares, preprint (2024). arXiv:2412.07733, https://arxiv.org/abs/2412.07733
8. Richard Montgomery, Transversals in Latin squares, survey preprint (2024). arXiv:2406.19873, https://arxiv.org/abs/2406.19873