Kevin Hendrey, Covering radius in the Hamming permutation space

Our problem can be described in terms of a two player game, played with the set ${\mathcal{S}}_n$ of permutations on $\{1,2,\dots ,n\}$. First, Player 1 selects a subset $S$ of ${\mathcal{S}}_n$ and shows it to Player 2. Next, Player 2 selects a permutation $p$ from ${\mathcal{S}}_n$ as different as possible from the permutations in $S$, and shows it to Player 1. Finally, Player 1 selects a permutation $q$ from $S$, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions, while keeping the size of $S$ small. The function $f(n,s)$ can be defined as the minimum size of a set $S\subseteq {\mathcal{S}}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions.

I will present some recent results on the function $f(n,s)$. We are particularly interested in determining the value $f(n,2)$, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound, showing that $f(n,2)⩾3n/4$. This talk is based on joint work with Ian M. Wanless.