1. Introduction
A well-known class of combinatorial objects is that of polyominoes. A 1 × 1 square in a square lattice is called cell. A polyomino is a connected plane figure built out of a finite number of cells joined along some of their edges. Introduced by Golomb more than half a century ago [1] (but see also the monograph [2] ), polyominoes continue to generate an endless list of mathematical problems.
Among the theoretical contributions of Golomb to the study of these objects are two tiling hierarchies, one for single polyominoes [3] and one for finite sets of polyominoes [4] . See Figure 1 for the last one. The levels considered are Rectangle (R), Half Strip (HS), Bent Strip (BS), Quadrant and Strip (Q + S), Quadrant (Q), Strip (S), Weak Rep-tile (WR), Strong Rep-tile (SR), Half Plane (HP), Plane (P) and Nothing (N). The sets of polyominoes classified by Golomb allow
![]()
Figure 1. Golomb’s tiling hierarchy for sets of polyominoes.
for translations, rotations and reflections in the coordinate axis for all tiles in the set.
Golomb showed all valid implications of tiling capabilities among the levels and that most of them (except for exhibiting a strong rep-tile set which does not tile rectangle and a weak rep-tile set that is not a strong rep-tile set) cannot be reversed.
In [5] we revisited Golomb’s tiling hierarchy for finite sets of polyominoes if only translations are allowed for polyominoes. For our study, due to the lack of symmetry, for each one of the levels HS, BS, Q, S, HP, more types of regions need to be considered. Their pictures are shown in Figure 2: four types of half strips HS(R), HS(L), HS(U), HS(D); four types of bent strips BS(I), BS(II), BS(III), BS(IV); four types of quadrants Q(I), Q(II), Q(III), Q(IV); two types of strips S(H), S(V); four types of half planes HP(R), HP(L), HP(U), HP(D).
We can also consider the level of Rep-tile. As we are not able to differentiate it from the level of Rectangle, we will neglect it in the future. In [5] we showed that there is no general relationship among the types corresponding to a fixed level for the existence of tilings. Then we showed the relationships from Golomb’s hierarchy that are still valid in this setup and those that are invalid. As a consequence of the results we showed two alternative tiling hierarchies (See Figure 3 and Figure 4). We also showed some unexpected additions to all of the above tiling hierarchies if deficient regions are considered. We recall that a deficient region is one missing a single cell.
When we speak about tiling a DEFICIENT-REGION we mean tiling SOME-DEFICIENT-REGION. This is in the spirit of Golomb’s approach. One can also consider the level ALL-DEFICIENT-REGION. The notions of
![]()
Figure 3. A tiling hierarchy for sets of polyominoes.
SOME-DEFICIENT-PLANE and ALL-DEFICIENT-PLANE coincide, as any two deficient planes are alike, but for other deficient levels the notions of SOME and ALL are distinct. This suggests the addition of the prefixes AD (ALL-DEFICIENT) and SD (SOME-DEFICIENT) to all levels and types of regions considered before, and to study the relationships between their tilings capabilities.
In both Golomb’s and our setups, the impact on tiling hierarchies of the addition of the prefix AD is minimal [5] . All implications in Figure 1, Figure 3 and Figure 4 remain valid and some of them even become equivalences. In this paper we concentrate on the tiling hierarchies shown in Figure 3 and Figure 4 after the addition of the prefix SD. For simplicity of notation we write only the prefix D. First we show that the types of deficient regions appearing inside each
![]()
Figure 4. Another tiling hierarchy for sets of polyominoes.
level have independent tiling properties. Second we show that almost all implications of tiling capabilities are invalid. Third we discuss some refinements of the tiling hierarchies if we look at deficient regions and restrict our attention to the class of tile sets that tile rectangles. This restriction allows to recover many of the implications of tiling capabilities that we have for non-deficient regions. All tile sets used in this paper are finite. Many of them are derived from tile sets already used by Golomb in [3] [4] . Several proofs of our statements are a bit tedious, but elementary, or follow from [3] [4] . For simplicity we will skip them. We do not make a consistent effort to reduce the numbers of tiles and the number of cells used by the sets of tiles.
2. Main Results
A first group of results shows that the types of deficient regions appearing inside each level have independent tiling properties.
Theorem 1. 1) For each type of deficient half strip there exists a set of polyominoes that tile that type but not the other three.
2) For each two types of deficient half strips there exists a set of polyominoes that tile these types but not the other two.
3) For each three types of deficient half strips there exists a set of polyominoes that tile these types but not the fourth.
Proof. 1) The set of tiles in Figure 5 tiles a deficient half strip of width 3 and type HS(R), but does not tile any other type of deficient half strip.
2) There are two cases to consider: the half-strips are adjacent and the half-strips are opposite. The set of tiles in Figure 6 tiles deficient half strips of width 3 and types HS(R) and HS(L), but does not tile other type of deficient half strip. The set of tiles in Figure 7 tiles deficient half strips of width 3 and types HS(R) and HS(U), but does not tile other type of deficient half strip.
![]()
Figure 5. A tile set that tiles DHS(R), but no other type of deficient half strip.
![]()
Figure 6. A tile set that tiles DHS(R) and DHS(L), but no other type of deficient half strip.
![]()
Figure 7. A tile set that tiles DHS(R) and DHS(U), but no other type of deficient half strip.
3) The tile set in Figure 8 tiles deficient half strips of width 3 and types HS(R), HS(L) and HS(U), but does not tile DHS(D).
In all cases, to show impossibility of tiling, look at the coverings of the corners of the half-strips. This gives a contradiction right away, or leads to the appearance of a half-strip pointing in the wrong direction.
Theorem 2. 1) For each type of deficient bent strip there exists a set of polyominoes that tile that type but not the other three.
2) For each two types of deficient bent strips there exists a set of polyominoes that tile these types but not the other two.
3) For each three types of deficient bent strips there exists a set of polyominoes that tile these types but not the fourth.
Proof. 1) The set of tiles in Figure 9 tiles a deficient bent strip of width 3 and type BS(I), but does not tile any other type of deficient bent strip.
2) There are two cases to consider: the bent strips are adjacent and the bent strips are opposite. The tile set in Figure 10 tiles deficient bent strips of width 3 and types BS(I) and BS(II), but does not tile other type of deficient bent strip. The tile set in Figure 11 tiles deficient bent strips of width 2 and types BS(I) and BS(III), but does not tile other type of bent strip.
![]()
Figure 8. A tile set that tiles DHS(R), DHS(L) and DHS(U), but not DHS(D).
![]()
Figure 9. A tile set that tiles DBS(I) but no other type of deficient bent strip.
![]()
Figure 10. A tile set that tiles DBS(I) and DBS(II), but no other type of deficient bent strip.
![]()
Figure 11. A tile set that tiles DBS(I) and DBS(III), but no other type of deficient bent strip.
3) The tile set in Figure 12 tiles deficient bent strips of width 3 and types BS(I), BS(II) and BS(III), but does not tile DBS(IV).
In all cases, to show impossibility of tiling, look at the coverings of the corner of the bent-strips. This leads to an immediate contradiction.
Theorem 3. 1) For each type of deficient quadrant there exists a set of polyominoes that tile that type but not the other three.
2) For each two types of deficient quadrants there exists a set of polyominoes that tile these types but not the other two.
3) For each three types of deficient quadrants strips there exists a set of polyominoes that tile these types but not the other.
Proof. 1) The tile set in Figure 13 tiles a deficient quadrant of type DQ(I), but does not tile any other type of deficient quadrant.
2) There are two cases to consider, depending on the quadrants being adjacent
![]()
Figure 12. A tile set that tiles DBS(I), DBS(II) and DBS(III), but does not tile DBS(IV).
![]()
Figure 13. A tile set that tiles DQ(I) but does not tile any other type of deficient quadrant.
or opposite. The tile set in Figure 14 tiles deficient quadrants of type Q(I) and Q(II) but does not tile any other type of deficient quadrant. The tile set in Figure 15 tiles deficient quadrants of types Q(I), Q(III) but does not tile any other type of deficient quadrant.
3) The tile set in Figure 16 tiles deficient quadrants of types Q(I), Q(II) and Q(III) but does not tile DQ(IV).
In all cases, to show impossibility of tiling, look at the coverings of the corner of the quadrants. This leads to an immediate contradiction. The tilings follow from [4] .
Theorem 4. For each type of deficient strip there exists a set of polyominoes that tile that type but not the other.
Proof. The tile set in Figure 17 tiles a deficient strip of type S(H) but does not tile DS(V). The gray cell in the first tile is missing from the tile. The tiling follows from [4] . To show impossibility of tiling, observe that there is no way to tile the walls of DS(V).
Theorem 5. 1) For each type of deficient half-plane there exists a set of polyominoes that tile that type but not the other three.
2) For each two types of deficient half-plane there exists a set of polyominoes that tile these types but not the other two.
3) For each three types of deficient half-plane there exists a set of polyominoes that tile these types but not the other.
Proof. 1) The tile set in Figure 18 tiles DHP(R) but does not tile other types of deficient half-plane.
2) There are two cases to consider, depending on the half-planes intersecting or being opposite. The tile set in Figure 19 tiles DHP(R), DHP(U) but does not tile any other type of deficient half-plane. The tile set in Figure 20 tiles DHP(R), DHP(L) but does not tile any other type of deficient half-plane.
3) The tile set in Figure 21 tiles half planes of types HP(R), HP(U) and HP(L) but does not tile DHP(D).
The tiling follows from [4] . To show impossibility of tiling, look at the tiling of the wall of the half-plane.
![]()
Figure 14. A tile set that tiles DQ(I), DQ(II) but does not tile any other type of deficient quadrant.
![]()
Figure 15. A tile set that tiles DQ(I), DQ(III) but does not tile any other type of deficient quadrant.
![]()
Figure 16. A tile set that tiles DQ(I), DQ(II), DQ(III) but does not tile DQ(IV).
![]()
Figure 17. A tile set that tiles DS(H) but does not tile DS(V).
![]()
Figure 18. A tile set that tiles DHP(R) but does not tile other types of deficient half-planes.
![]()
Figure 19. A tile set that tiles DHP(R), DHP(U) but does not tile other type of deficient half-plane.
![]()
Figure 20. A tile set that tiles DHP(R) and DHP(L) but does not tile other type of deficient half-plane.
![]()
Figure 21. A tile set that tiles DHP(R), DHP(U) and DHP(L) but does not tile DHP(D).
A second group of results investigates for deficient regions the validity of the implications of tiling capabilities in in Figure 3 and Figure 4. The following result shows that all the implications in Figure 3 are invalid.
Theorem 6. The following implications are invalid:
1) DR → DHS(*), where *Î{R, L, U, D};
2) DHS(*) → DQ(**), where *Î{R, L, U, D}, **Î{I, II, III, IV};
3) DQ(*) → DHP(**), where *Î{R, L, U, D}, **Î{I, II, III, IV};
4) DHP(**) → DP, where **Î{I, II, III, IV};.
Proof. 1) A counterexample is given by a tile set consisting of a single deficient rectangle. 2) The tile set in Figure 22 tiles a width 3 deficient half strip of type HS(R) (see Figure 23) but does not tile any deficient quadrant. To prove the last part, observe that any quadrant has a vertical wall. Any attempt to tile it creates an infinity of cells adjacent to the wall that cannot be covered. This shows that the implication DHS(R) → DQ(**) is not valid. The other cases follow using rotations of the tile set in Figure 4 by 90˚, 180˚, 270˚.
3) The tile set in Figure 24 tiles a deficient quadrant of type Q(I) (see Figure 25) but does not tile any deficient half plane. To prove the last part, look at the covering of the wall of the half plane. Once a deficient cell adjacent to the wall appears, one more deficient cell close to the wall is forced to appear. But if the whole row (column) adjacent to the wall is covered, then the first three rows (columns) are covered, reducing the problem to a new half plane. This shows that the implication DQ(I) → DHP(**) is not valid. The other cases follow using rotations of the tile set in Figure 6 by 90˚, 180˚, 270˚.
4) The tile set in Figure 26 tiles a deficient half plane of type HP(U) (see Figure 27) but does not tile any deficient plane. To prove the last part, observe that a neighborhood of size 10 of the missing cell is forced to contain at lest one more cell that cannot be tiled. This shows that the implication DHP(U) → DP is not valid. The other cases follow using rotations of the tile set in Figure 8 by 90˚, 180˚, 270˚.
We observe that all tile sets used for counterexamples tile not just the respective
![]()
Figure 22. A tile set that tiles a deficient half strip, but no deficient quadrant.
![]()
Figure 23. A tiling of a deficient half strip.
![]()
Figure 24. A tile set that tiles a deficient quadrant, but no deficient half plane.
![]()
Figure 26. A tile set that tiles a deficient half plane, but no deficient plane.
![]()
Figure 27. A tiling of a deficient half plane.
deficient regions, but also instances of the respective regions which have an arbitrary finite number of missing cells.
We show now that almost all the implications in Figure 4 are invalid, with the exception of those containing the level S(V)-and-SV(H), which obviously remain true, and the implication DS(**) → DHP(***), where **Î{H,V}, ***Î{U,D,L,R}.
Theorem 7. The following implications are invalid
1) DR → DBS(*), where *Î{I,II,II,IV};
2) DBS(*) → DQ(**), where *,**Î{I,II,II,IV};
3) DS(V) and DQ(*) → DS(H), where *Î{I,II,II,IV};
4) DS(H) and DQ(*) → DS(V), where *Î{I,II,II,IV};
5) DQ(*) → DHP(***), where *Î{I,II,II,IV}, ***Î{U,D,L,R};
6) DHP(***) → DP, where ***Î{U,D,L,R}.
The following implication is valid:
7) DS(H) → DHP(***), where ***Î{U,D};
8) DS(V) → DHP(***), where ***Î{L,R}.
Proof. 1) A counterexample is given by a tile set consisting of a single deficient rectangle.
2) One can use the tile set in Figure 24, after eliminating the first tile. A tiling of a width 3 deficient bent strip of type BS(I) is shown in Figure 25. To prove the last part, observe that a neighborhood of the missing cell of size 10 is forced to contain at least one more deficient cell. This shows that the implication DBS(I) → DQ(**) is not valid. The other cases follow using rotations of the previous tile set by 90˚, 180˚, 270˚.
3), 4) Figure 28 shows a tile set that tiles a deficient quadrant of type (I) and a deficient vertical strip, but no deficient horizontal strip and Figure 29 shows a tile set that tiles a deficient quadrant of type (I) and a deficient horizontal strip, but no deficient vertical strip. The tilings of the deficient quadrant are shown in Figure 25 and the tilings of the deficient strips are shown in Figure 30. The other cases follow using rotations of the previous tile set by 90˚, 180˚, 270˚.
5) This is Theorem 2.1, 3).
6) This is Theorem 2.1, 4).
![]()
Figure 28. A tile set that tiles a deficient quadrant of type (I) and a deficient vertical strip, but no deficient horizontal strip.
![]()
Figure 29. A tile set that tiles a deficient quadrant of type (I) and a deficient horizontal strip, but no deficient vertical strip.
![]()
Figure 30. A tiling of a deficient horizontal strip and a tiling of a deficient vertical strip.
7), 8) One can show, using the same argument as in the proof of [Theorem 3, 3], that a tile set that tiles a deficient strip of type DS(H) also tiles a horizontal (non-deficient) strip of same width. Then the strips can be repeated on the top or at the bottom of the deficient strip to fill a deficient half plane of type HP(U) or HP(D). A similar argument is valid for 8).
We show in [6] that the tile set T4 consisting of four ribbon L-tetrominoes, with only translations allowed, tile the opposite deficient quadrants DQ(II) and DQ(IV), allowing for any missing cell, but does not tile any of the other two deficient quadrants DQ(I) and DQ(III), no matter what cell is missing. We also show that T4 does not tile any deficient half-strip, deficient bent-strip or deficient strip, while it tiles all deficient half-planes and deficient planes. This raises the question if refinements of the tiling hierarchies are possible.
As the tile set T4 already tiles rectangles, we study implications of tiling capabilities for deficient regions of tile sets that tile rectangles and consist of simply connected tiles. It is shown in [6] that a tile set that tiles rectangles also tiles deficient planes. We asked in [6] if it is possible for such a tile set to not tile any other deficient region. The following result answers this question.
Proposition 8. There exists a tile set with all symmetries allowed that tiles some rectangles, some deficient rectangles, and consists of simply connected tiles, but does not tile any other deficient region in Golomb’s hierarchy, except a deficient plane. If only translations are allowed, the tile set does not tile any of the deficient regions in Figure 3 and Figure 4, except a deficient plane.
Proof. The tile set is shown in Figure 31. We observe that the tile set in [Figure 6 and Figure 25] tiles a deficient plane but no other region, deficient or not, in Figure 1, Figure 3 and Figure 4.
Next theorem shows the validity of the rest of the implications in Figure 1.
Theorem 9. The following implications are valid and neither one of them can be reversed:
1) R-and-DHS → R-and-DQ;
2) R-and-DBS → R-and-DQ;
3) R-and-DS → R-and-DHP;
4) R-and-DQ → R-and-DHP;
5) R-and-DHP → R-and-DP.
The following implications are invalid:
6) R-and-DHS → R-and-DBS;
![]()
Figure 31. A tile set that tiles a rectangle, a deficient rectangle and a deficient plane, but no other deficient region.
7) R-and-DBS → R-and-DS.
Proof. 1)-5). The proofs for the valid implications are immediate. To show that 1) cannot be reversed use the tile set in Figure 13, to which we add a new tile made of a 3 × 3 square. To show that 2) cannot be reversed use the tile set in Figure 9 to which we add a 4 × 4 square. The show that 3) and 4) cannot be reversed use the tile set in Figure 18 to which we add a new tile made of a 3 × 3 square. To show that 5) cannot be reversed use the tile set in [Figure 6 and Figure 25] to which we add a new tile made of a 3 × 3.
6) The tile set in Figure 32 tiles a rectangle and a deficient half strip, but does not tile any deficient bent strip.
7) The tile set in Figure 33 tiles a rectangle and a deficient bent strip, but does not tile any deficient strip.
Theorem 9 allows to recover some of the hierarchy in Figure 1. See Figure 34.
Next theorem shows the validity of the rest of the implications in Figure 3.
Theorem 10. If R1 → R2 is an implication in Figure 3 different from R → HS(*), *Î{R,L,U,D}, then R-and-DR1 → SR-and-DR2 is a valid implication. Neither one of these implications can be reversed.
Proof. The proofs for the valid implications are immediate. To show that the implications cannot be reversed use the tile sets used in Theorem 2.9. Theorem \ref{thm:ref2} allows to recover the hierarchy in Figure 3. See Figure 35.
Next theorem shows the validity of the implications in Figure 4 that are not obvious or discussed above.
Theorem 11. The following implications are valid:
1) R-and-DBS(*) → R-and-DQ(*), *Î{I,II,III,IV};
The following implications are invalid:
2) R-and-DBS(*) → R-and-DS(**), *Î{ I,II,III,IV}, **Î{H,V}.
Proof. 1) The proof is immediate.
2) See Figure 36.
![]()
Figure 32. A tile set that tiles SR-SDHS(R), but does not tile any deficient bent strip.
![]()
Figure 33. A tile set that tiles R-DBS(R), but does not tile any deficient strip.
![]()
Figure 34. A tiling hierarchy for tile sets that tiles a rectangle derived from Figure 1.
![]()
Figure 35. A tiling hierarchy for tile sets that tiles a rectangle derived from Figure 3.
![]()
Figure 36. A tile set that tiles R-DBS(I), but does not tile any deficient strip.
3. Conclusion
The results about tiling deficient regions by T4 are based on a coloring invariant introduced in [7] . An interesting problem is to extend these results to other tile sets introduced in [8] [9] [10] . These are natural simple tile sets with potentially interesting tiling capabilities. For some of these tile sets coloring invariants are not available [11] [12] . Some conjectures about tiling deficient regions by Tn can be found in [13] .
Acknowledgements
V. Nitica was partially supported by Simons Foundation Grant 208729.