Covering radius in the Hamming permutation space

Kevin Hendrey, Ian M. Wanless

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Let Sn 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⊆Sn with the property that for any ρ∈Sn 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 languageEnglish
Article number103025
Pages (from-to)1-9
Number of pages9
JournalEuropean Journal of Combinatorics
Volume84
DOIs
Publication statusPublished - 1 Feb 2020

Cite this

@article{3f5ff296c82a46deae8f1b1fd2c177a3,
title = "Covering radius in the Hamming permutation space",
abstract = "Let Sn 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⊆Sn with the property that for any ρ∈Sn 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{\'e}zdy and Snevily, which implies several famous conjectures about Latin squares. We prove that the odd n case of the K{\'e}zdy–Snevily Conjecture implies the whole conjecture. We also show that f(n,2)>3n∕4 for all n, that s! [Formula presented] [Formula presented] if s⩾3.",
author = "Kevin Hendrey and Wanless, {Ian M.}",
year = "2020",
month = "2",
day = "1",
doi = "10.1016/j.ejc.2019.103025",
language = "English",
volume = "84",
pages = "1--9",
journal = "European Journal of Combinatorics",
issn = "0195-6698",
publisher = "Elsevier",

}

Covering radius in the Hamming permutation space. / Hendrey, Kevin; Wanless, Ian M.

In: European Journal of Combinatorics, Vol. 84, 103025, 01.02.2020, p. 1-9.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Covering radius in the Hamming permutation space

AU - Hendrey, Kevin

AU - Wanless, Ian M.

PY - 2020/2/1

Y1 - 2020/2/1

N2 - Let Sn 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⊆Sn with the property that for any ρ∈Sn 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! [Formula presented] [Formula presented] if s⩾3.

AB - Let Sn 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⊆Sn with the property that for any ρ∈Sn 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! [Formula presented] [Formula presented] if s⩾3.

UR - http://www.scopus.com/inward/record.url?scp=85072782852&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2019.103025

DO - 10.1016/j.ejc.2019.103025

M3 - Article

AN - SCOPUS:85072782852

VL - 84

SP - 1

EP - 9

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

M1 - 103025

ER -