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 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
}
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 journal › Article › Research › peer-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 -