Hypercube packings and coverings with higher dimensional rooks

zbMATH Open1444.05037arXiv1801.10607MaRDI QIDQ3300685FDOQ3300685

Authors: Mehtaab Sawhney, David Stoner 

Publication date: 29 July 2020

Abstract: We introduce a generalization of classical $q$-ary codes by allowing points to cover other points that are Hamming distance $1$ or $2$ in a freely chosen subset of all directions. More specifically, we generalize the notion of $1$-covering, $1$-packing, and $2$-packing in the case of $q$-ary codes. In the covering case, we establish the analog of the sphere-packing bound and in the packing case, we establish an analog of the singleton bound. Given these analogs, in the covering case we establish that the sphere-packing bound is asymptotically never tight except in trivial cases. This is in essence an analog of a seminal result of Rodemich regarding $q$-ary codes. In the packing case we establish for the $1$-packing and $2$-packing cases that the analog of the singleton bound is tight in several possible cases and conjecture that these bounds are optimal in general.

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

Recommendations

• scientific article; zbMATH DE number 2096443
• Bounds on packings and coverings by spheres in \(q\)-ary and mixed Hamming spaces
• Weighted coverings and packings
• Packing points into a unit cube in higher space
• Packings and coverings over an arbitrary alphabet

zbMATH Keywords

sphere packing bound\(q\)-ary codes

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of packing and covering (05B40) Other types of codes (94B60)

Cites Work

• Maximum distance<tex>q</tex>-nary codes
• Upper bounds for football pool problems and mixed covering codes
• More coverings by rook domains
• The football pool problem for 7 and 8 matches
• Coverings by rook domains
• New upper bounds for binary covering codes
• Lower bounds for the football pool problem for 7 and 8 matches
• Lower bounds on covering codes via partition matrices
• A Combinatorial Problem in Matching
• A new upper bound for the football pool problem for nine matches

Cited In (3)

• Hyper-rook Domain Inequalities
• More coverings by rook domains
• Packings and coverings over an arbitrary alphabet

This page was built for publication: Hypercube packings and coverings with higher dimensional rooks

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