Journal of Combinatorial Theory, Series A
(2005), no. 1, pp. 89-105.

Klarner Systems and Tiling Boxes with Polyominoes,
by Michael Reid

Journal of Combinatorial Theory, Series A
(2005), no. 1, pp. 89-105.

Abstract

Given a protoset *T*, of *n*-dimensional polyominoes,
what boxes can be tiled by *T* ?
A fundamental result of Klarner and Göbel [2] asserts that the answer
can always be described by giving a finite list of "prime" boxes.
All other boxes that can be tiled can be deduced from this finite
collection of prime boxes.
Unfortunately, the proof in the original paper of
Klarner and Göbel [2] has a gap for dimensions 3 and higher.
Klarner repairs the proof in an unpublished technical report [1].

We give a new, simple and direct proof of this fundamental result, at the
same time obtaining a slightly stronger statement.
Moreover we show that there is no upper bound to the number of prime
boxes of a protoset, even when restricting to a narrow class of protosets
(namely, singleton protosets in 2 dimensions).
In the last section, we determine the prime rectangles for some singleton
protosets of small polyominoes, and show the variety of techniques that
are used.

References

[1]
David A. Klarner,
A Finite Basis Theorem Revisited,
Technical Report CS-TR-73-338,
Stanford University, February 1973.

[2]
D.A. Klarner and F. Göbel,
Packing boxes with congruent figures,
Indagationes Mathematicae
(1969) pp. 465-472.
[Math Reviews]

Updated January 6, 2008.