Back
 OJDM  Vol.6 No.3 , July 2016
Signed Tilings by Ribbon L n-Ominoes, n Even, via Gröbner Bases
Abstract: Let Tn be the set of ribbon L-shaped n-ominoes for some n4 even, and let T+n be Tn with an extra 2 x 2 square. We investigate signed tilings of rectangles by Tn and T+n . We show that a rectangle has a signed tiling by Tn if and only if both sides of the rectangle are even and one of them is divisible by n, or if one of the sides is odd and the other side is divisible by . We also show that a rectangle has a signed tiling by T+n, n≥6 even, if and only if both sides of the rectangle are even, or if one of the sides is odd and the other side is divisible by . Our proofs are based on the exhibition of explicit GrÖbner bases for the ideals generated by polynomials associated to the tiling sets. In particular, we show that some of the regular tiling results in 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, cannot be obtained from coloring invariants.
Cite this paper: Gill, K. and Nitica, V. (2016) Signed Tilings by Ribbon L n-Ominoes, n Even, via Gröbner Bases. Open Journal of Discrete Mathematics, 6, 185-206. doi: 10.4236/ojdm.2016.63017.
References

[1]   Golomb, S.W. (1954) Checker Boards and Polyominoes. American Mathematical Monthly, 61, 675-682.
http://dx.doi.org/10.2307/2307321

[2]   Golomb, S.W. (1994) Polyominoes, Puzzles, Patterns, Problems, and Packings. Princeton University Press, Princeton.

[3]   Pak, I. (2000) Ribbon tile Invariants. Transactions of the American Mathematical Society, 352, 5525-5561.
http://dx.doi.org/10.1090/S0002-9947-00-02666-0

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

[5]   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.
http://dx.doi.org/10.4236/ojdm.2015.52002

[6]   Golomb, S.W. (1964) Replicating Figures in the Plane. Mathematical Gazette, 48, 403-412.
http://dx.doi.org/10.2307/3611700

[7]   Nitica, V. (2003) Rep-Tiles Revisited, in the Volume MASS Selecta: Teaching and Learning Advanced Undergraduate Mathematics. American Mathematical Society.

[8]   Conway, J.H. and Lagarias, J.C. (1990) Tilings with Polyominoes and Combinatorial Group Theory. Journal of Combinatorial Theory, Series A, 53, 183-208.
http://dx.doi.org/10.1016/0097-3165(90)90057-4

[9]   Bodini, O. and Nouvel, B. (2004) Z-Tilings of Polyominoes and Standard Basis, in Combinatorial Image Analysis. Springer, Berlin, 137-150.
http://dx.doi.org/10.1007/978-3-540-30503-3_11

[10]   Nitica, V. (2015) Signed Tilings by Ribbon L n-Ominoes, n Odd, via GrÖbner Bases. arXiv:1601.00558v2.

[11]   Barnes, F.W. (1982) Algebraic Theory of Brick Packing I. Discrete Math, 42, 7-26.
http://dx.doi.org/10.1016/0012-365X(82)90049-8

[12]   Barnes, F.W. (1982) Algebraic Theory of Brick Packing II. Discrete Math, 42, 129-144.
http://dx.doi.org/10.1016/0012-365X(82)90211-4

[13]   Becker, T. and Weispfenning, V. (In Cooperation with Krendel, H.) (1993) GrÖbner Bases. Springer-Verlag, Berlin.

[14]   Dizdarevic, M.M., Timotijevic, M. and Zivaljevic, R.T. (2016) Signed Polyominotilings by n-in-Line Polyominoesand GrÖbner Bases. Publications de l’Institut Mathematique, Nouvelle Série, 99, 31-42.
http://dx.doi.org/10.2298/PIM1613031M

[15]   Seidenberg, A. (1974) Constructions in Algebra. Transactions of the American Mathematical Society, 197, 273-313.
http://dx.doi.org/10.1090/S0002-9947-1974-0349648-2

[16]   Klarner, D.A. (1969) Packing a Rectangle with Congruent N-Ominoes. Journal of Combinatorial Theory, 7, 107-115.
http://dx.doi.org/10.1016/S0021-9800(69)80044-X

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

 
 
Top