Covering radius in the Hamming permutation space

DOI10.1016/J.EJC.2019.103025MaRDI QIDQ2011145zbMATH OpenOpenAlexWikidataFDO

Authors Kevin Hendrey, Ian M. Wanless

Publication date 28 November 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.09040

zbMATH Keywords

Hamming distance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: 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 $Ssubseteqmathcal{S}_n$ with the property that for any $hoinmathcal{S}_n$ there exists some $sigmainS$ such that the Hamming distance between $ho$ and $sigma$ is at most $n-s$. The value of $f(n,2)$ is the subject of a conjecture by K'ezdy and Snevily, which implies several famous conjectures about latin squares. We prove that the odd $n$ case of the K'ezdy-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 $1leqsleqn-2$ and that [f(n,s)>leftlfloor frac{2+sqrt{2s-2}}{2} ight floor frac{n}{2}] if $sgeq3$.

Recommendations

• Transversals of Latin squares and covering radius of sets of permutations
• Covering radius for sets of permutations
• On the maximum number of permutations with given maximal or minimal distance
• Intersection theorems in permutation groups
• A random construction for permutation codes and the covering radius

Cites work

• A random construction for permutation codes and the covering radius
• A survey on packing and covering problems in the Hamming permutation space
• Covering radius for sets of permutations
• Degree conditions for matchability in 3-partite hypergraphs
• Intersecting families of permutations
• Latin squares with no transversals
• On the ratio of optimal integral and fractional covers
• The multicovering radius problem for some types of discrete structures
• Transversals in Latin squares: a survey
• Transversals of Latin squares and covering radius of sets of permutations

Cited in

(7)

• Covering radius for sets of permutations
• Unit sphere packings and coverings of the Hamming space
• Transversals of Latin squares and covering radius of sets of permutations
• Covering radius of permutation groups with infinity-norm
• Proof of a conjecture of Kløve on permutation codes under the Chebychev distance
• All group‐based latin squares possess near transversals
• The covering radius of permutation designs

This page was built for publication: Covering radius in the Hamming permutation space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011145)