On multifold packings of radius-1 balls in Hamming graphs

Denis S. Krotov, Vladimir N. Potapov

A $\lambda$-fold $r$-packing 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 than $\lambda$ times. The well-known $r$-error-correcting codes correspond to the case $\lambda=1$. We propose asymptotic bounds for the maximum size of a $q$-ary $2$-fold $1$-packing as $q$ grows; prove that a $q$-ary distance-$2$ MDS code of length is an optimal $n$-fold $1$-packing if $q\ge 2n$; find that the maximum size of a binary $2$-fold $1$-packing of length $9$ is $96$; and derive upper bounds for the size of a binary $\lambda$-fold $1$-packing. We prove some properties of $1$-perfect unitrades, which are a special case of two-fold $1$-packings. Keywords: Hamming graph, multifold ball packings, two-fold ball packings, $l$-list decodable codes, completely regular codes, linear programming bound, unitrades, bitrades.

arrow_drop_up