Back
 OJDM  Vol.8 No.2 , April 2018
Revisiting a Tiling Hierarchy (II)
Abstract: In a recent paper, we revisited Golomb’s hierarchy for tiling capabilities of finite sets of polyominoes. We considered the case when only translations are allowed for the tiles. In this classification, for several levels in Golomb’s hierarchy, more types appear. We showed that there is no general relationship among tiling capabilities for types corresponding to same level. Then we found the relationships from Golomb’s hierarchy that remain valid in this setup and found those that fail. As a consequence we discovered two alternative tiling hierarchies. The goal of this note is to study the validity of all implications in these new tiling hierarchies if one replaces the simply connected regions by deficient ones. We show that almost all of them fail. If one refines the hierarchy for tile sets that tile rectangles and for deficient regions then most of the implications of tiling capabilities can be recovered.
Cite this paper: Nitica, V. (2018) Revisiting a Tiling Hierarchy (II). Open Journal of Discrete Mathematics, 8, 48-63. doi: 10.4236/ojdm.2018.82005.
References

[1]   Golomb, S.W. (1954) Checker Boards and Polyominoes. American Mathematical Monthly, 61, 675-682.
https://doi.org/10.1080/00029890.1954.11988548

[2]   Golomb, S.W. (1994) Polyominoes, Puzzeles, Patterns, Problems, and Packings. 2nd Edition, Princeton University Press, NJ.

[3]   Golomb, S.W. (1966) Tiling with Polyominoes. Journal of Combinatorial Theory, 1, 280-296.
https://doi.org/10.1016/S0021-9800(66)80033-9

[4]   Golomb, S.W. (1970) Tiling with Sets of Polyominoes. Journal of Combinatorial Theory, 9, 60-71.
https://doi.org/10.1016/S0021-9800(70)80055-2

[5]   Nitica, V. (2018) Revisiting a Tiling Hierarchy. IEEE Transactions on Information Theory, 64, 3162-3169.
https://doi.org/10.1109/TIT.2018.2795612

[6]   Nitica, V. (2017) The Tilings of Deficient Squares by Ribbon L-Tetrominoes Are Diagonally Cracked. Open Journal of Discrete Mathematics, 7, 165-176.
https://doi.org/10.4236/ojdm.2017.73015

[7]   Chao, M., Levenstein, D., Nitica, V. and Sharp, R. (2013) A Coloring Invariant for Ribbon L-Tetrominoes. Discrete Mathematics, 313, 611-621.
https://doi.org/10.1016/j.disc.2012.12.007

[8]   Nitica, V. (2015) Every Tiling of the First Quadrant by Ribbon L n-Ominoes Follows the Rectangular Pattern. Open Journal of Discrete Mathematics, 5, 11-25.
https://doi.org/10.4236/ojdm.2015.52002

[9]   Nitica, V. (2016) On Tilings of Quadrants and Rectangles and Rectangular Pattern. Open Journal of Discrete Mathematics, 6, 351-371.
https://doi.org/10.4236/ojdm.2016.64028

[10]   Calderon, A., Fairchild, S., Nitica, V. and Simon, S. (2016) Tilings of Quadrants by L-Ominoes and Notched Rectangles. Topics in Recreational Mathematics, 7, 39-75.

[11]   Gill, K. and Nitica, V. (2016) Signed Tilings by Ribbon L n-Ominoes, n Even, via Grobner Bases. Open Journal of Discrete Mathematics, 6, 185-206.
https://doi.org/10.4236/ojdm.2016.63017

[12]   Nitica, V. (2016) Signed Tilings by Ribbon L n-Ominoes, n Odd, via Grobner Bases. Open Journal of Discrete Mathematics, 6, 297-313.
https://doi.org/10.4236/ojdm.2016.64025

[13]   Junius, P. and Nitica, V. (2017) Tiling Rectangles with Gaps by Ribbon Right Trominoes. Open Journal of Discrete Mathematics, 7, 87-102.
https://doi.org/10.4236/ojdm.2017.72010

 
 
Top