Covering radius in the Hamming permutation space
Let symn denote the set of permutations of {1,2,...,n}.
The function f(n,s) is defined to be the minimum size of a subset S
of symn with the property that for any ρ in
symn there exists some σ in S such that the Hamming
distance between ρ and σ is at most n-s. The value of
f(n,2) is the subject of a conjecture by Kézdy and Snevily,
which implies several famous conjectures about Latin squares.
We prove that the odd n case of the Kézdy-Snevily Conjecture
implies the whole conjecture. We also show that f(n,2)>3n/4 for
all n, that s!< f(n,s)< 3s!(n-s)log n for 1≤ s≤ n-2 and
that f(n,s)>floor((2+√(2s-2))/2)n/2 if s≥3.