### Abstract

Let S_{n} 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⊆S_{n} with the property that for any ρ∈S_{n} there exists some σ∈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)logn for 1⩽s⩽n−2 and that f(n,s)> [Formula presented] [Formula presented] if s⩾3.

Original language | English |
---|---|

Article number | 103025 |

Pages (from-to) | 1-9 |

Number of pages | 9 |

Journal | European Journal of Combinatorics |

Volume | 84 |

DOIs | |

Publication status | Published - 1 Feb 2020 |

## Cite this

Hendrey, K., & Wanless, I. M. (2020). Covering radius in the Hamming permutation space.

*European Journal of Combinatorics*,*84*, 1-9. [103025]. https://doi.org/10.1016/j.ejc.2019.103025