On Multifold Packings of Radius-1 Balls in Hamming Graphs

DOI10.1109/TIT.2020.3046260MaRDI QIDQ5001741zbMATH OpenOpenAlexFDO

Authors Vladimir N. Potapov, Denis S. Krotov

Publication date 23 July 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic bounds for maximum sizeoptimal binary 2-fold 1-packings

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Linear codes (general theory) (94B05) Bounds on codes (94B65)

Abstract: A $lambda$-fold $r$-packing (multiple radius-$r$ covering) in a Hamming metric space is a code $C$ such that the radius-$r$ balls centered in $C$ cover each vertex of the space by not more (not less, respectively) than $lambda$ times. The well-known $r$-error-correcting codes correspond to the case $lambda=1$, while in general multifold $r$-packing are related with list decodable codes. We (a) propose asymptotic bounds for the maximum size of a $q$-ary $2$-fold $1$-packing as $q$ grows; (b) prove that a $q$-ary distance-$2$ MDS code of length $n$ is an optimal $n$-fold $1$-packing if $qge2n$; (c) derive an upper bound for the size of a binary $lambda$-fold $1$-packing and a lower bound for the size of a binary multiple radius-$1$ covering (the last bound allows to update the small-parameters table); (d) classify all optimal binary $2$-fold $1$-packings up to length $9$, in particular, establish the maximum size $96$ of a binary $2$-fold $1$-packing of length $9$; (e) prove some properties of $1$-perfect unitrades, which are a special case of $2$-fold $1$-packings. Keywords: Hamming graph, multifold ball packings, two-fold ball packings, list decodable codes, multiple coverings, completely regular codes, linear programming bound

Cited in

(7)

• Tight packings of Hamming spheres
• On the Weight of Halfspaces over Hamming Balls
• Domination mappings into the Hamming ball: existence, constructions, and algorithms
• Perfect 2‐colorings of Hamming graphs
• The classification of orthogonal arrays \(\mathrm{OA}(2048,14,2,7)\) and some completely regular codes
• On degree-3 and (n - 4)-correlation-immune perfect colorings of n-cubes
• Multifold 1-perfect codes

This page was built for publication: On Multifold Packings of Radius-1 Balls in Hamming Graphs

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