𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tiling Hamming Space with Few Spheres

✍ Scribed by Henk D.L Hollmann; János Körner; Simon Litsyn

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
272 KB
Volume
80
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if the collection of all binary vectors of length n is partitioned into k spheres, then either k 2 or k n+2. Moreover, such partitions with k=n+2 are essentially unique.

1997 Academic Press

Recently there has been some interest in the combinatorics of the geometry of the Hamming space, e.g., [10], and in particular, in tilings of this space [8]. Here, we investigate partitions of the Hamming space into spheres with possibly different radii. Such a partition is sometimes called a generalized perfect code, see e.g. [1,3,6,13,15]. Generalized spherepacking bounds can be found in [7]. Our aim in this note is to prove the following result (the gap-theorem):

Theorem 1. If the binary Hamming space H(n, 2) is partitioned into M spheres, then article no. TA972816 388 0097-3165Â97 25.00

📜 SIMILAR VOLUMES

On partitions of the q-ary Hamming space
On partitions of the q-ary Hamming space into few spheres
✍ Andreas Klein; Markus Wessler 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

## Abstract In this paper, we present a generalization of a result due to Hollmann, Körner, and Litsyn [9]. They prove that each partition of the __n__‐dimensional binary Hamming space into spheres consists of either one or two or at least __n__ + 2 spheres. We prove a __q__‐ary version of that gap

Good coverings of Hamming spaces with sp
Good coverings of Hamming spaces with spheres
✍ Gérard Cohen; Peter Frankl 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 421 KB

We give a non-constructive proof ot the existence of good coverings of binary and non binary Hamming spaces by spheres centered on a subspace (linear codes). The results hold for tiles other than spheres.

Tiling space with notched cubes
Tiling space with notched cubes
✍ James H. Schmerl 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 729 KB

Stein (1990) discovered (n -l)! lattice tilings of R" by translates of the notched n-cube which are inequivalent under translation. We show that there are no other inequivalent tilings of IF!" by translates of the notched cube.

H-spaces with few cells
H-spaces with few cells
✍ J.F. Adams 📂 Article 📅 1962 🏛 Elsevier Science 🌐 English ⚖ 343 KB