Let $mathcal{S}_n$ denote the set of permutations of ${1,2,dots,n}$. The function $f(n,s)$ is defined to be the minimum size of a subset $Ssubseteq mathcal{S}_n$ with the property that for any $rhoin mathcal{S}_n$ there exists some $sigmain S$ such that the Hamming distance between $rho$ and $sigma$ is at most $n-s$. The value of $f(n,2)$ is the subject of a conjecture by Kezdy and Snevily, which implies several famous conjectures about latin squares. We prove that the odd $n$ case of the Kezdy-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 $1leq sleq n-2$ and that [f(n,s)>leftlfloor frac{2+sqrt{2s-2}}{2}rightrfloor frac{n}{2}] if $sgeq 3$.
Download