Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Nonemptiness problems of plane square tiling with two colors


Authors: Wen-Guei Hu and Song-Sun Lin
Journal: Proc. Amer. Math. Soc. 139 (2011), 1045-1059
MSC (2010): Primary 37B10, 37B50, 52C20, 37E15, 05B45, 52C23
DOI: https://doi.org/10.1090/S0002-9939-2010-10518-X
Published electronically: August 6, 2010
MathSciNet review: 2745655
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This investigation studies nonemptiness problems of plane square tiling. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges of $ p$ colors are arranged side by side such that adjacent tiles have the same colors. Given a set of Wang tiles $ \mathcal{B}$, the nonemptiness problem is to determine whether or not $ \Sigma(\mathcal{B})\neq\emptyset$, where $ \Sigma(\mathcal{B})$ is the set of all global patterns on $ \mathbb{Z}^{2}$ that can be constructed from the Wang tiles in $ \mathcal{B}$.

When $ p\geq 5$, the problem is well known to be undecidable. This work proves that when $ p=2$, the problem is decidable. $ \mathcal{P}(\mathcal{B})$ is the set of all periodic patterns on $ \mathbb{Z}^{2}$ that can be generated by $ \mathcal{B}$. If $ \mathcal{P}(\mathcal{B})\neq\emptyset$, then $ \mathcal{B}$ has a subset $ \mathcal{B}'$ of minimal cycle generator such that $ \mathcal{P}(\mathcal{B}')\neq\emptyset$ and $ \mathcal{P}(\mathcal{B}'')=\emptyset$ for $ \mathcal{B}''\subsetneqq \mathcal{B}'$. This study demonstrates that the set of all minimal cycle generators $ \mathcal{C}(2)$ contains $ 38$ elements. $ \mathcal{N}(2)$ is the set of all maximal noncycle generators: if $ \mathcal{B}\in\mathcal{N}(2)$, then $ \mathcal{P}(\mathcal{B})=\emptyset$ and $ \widetilde{\mathcal{B}}\supsetneqq \mathcal{B}$ implies $ \mathcal{P}(\widetilde{\mathcal{B}})\neq\emptyset$. $ \mathcal{N}(2)$ has eight elements. That $ \Sigma(\mathcal{B})=\emptyset$ for any $ \mathcal{B}\in\mathcal{N}(2)$ is proven, implying that if $ \Sigma(\mathcal{B})\neq\emptyset$, then $ \mathcal{P}(\mathcal{B})\neq\emptyset$. The problem is decidable for $ p=2$: $ \Sigma(\mathcal{B})\neq\emptyset$ if and only if $ \mathcal{B}$ has a subset of minimal cycle generators. The approach can be applied to corner coloring with a slight modification, and similar results hold.


References [Enhancements On Off] (What's this?)

  • 1. J.C. Ban and S.S. Lin, Patterns generation and transition matrices in multi-dimensional lattice models, Discrete Contin. Dyn. Syst. 13 (2005), no. 3, 637-658. MR 2152335 (2006f:37113)
  • 2. J.C. Ban, W.G. Hu, S.S. Lin and Y.H. Lin, Zeta functions for two-dimensional shifts of finite type, preprint (2008).
  • 3. J.C. Ban, S.S. Lin and Y.H. Lin, Patterns generation and spatial entropy in two-dimensional lattice models, Asian J. Math. 11 (2007), 497-534. MR 2372728 (2010d:37030)
  • 4. R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc., 66 (1966). MR 0216954 (36:49)
  • 5. K. Culik II, An aperiodic set of $ 13$ Wang tiles, Discrete Mathematics, 160 (1996), 245-251. MR 1417576 (97f:05045)
  • 6. B. Grünbaum and G. C. Shephard, Tilings and Patterns, New York: W. H. Freeman, 1986. MR 992195 (90a:52027)
  • 7. J. Kari, A small aperiodic set of Wang tiles, Discrete Mathematics, 160 (1996), 259-264. MR 1417578 (97f:05046)
  • 8. A. Lagae and P. Dutré, An alternative for Wang tiles: Colored edges versus colored corners, ACM Trans. Graphics, 25 (2006), no. 4, 1442-1459.
  • 9. A. Lagae, J. Kari and P. Dutré, Aperiodic sets of square tiles with colored corners, Report CW 460, Department of Computer Science, K.U. Leuven, Leuven, Belgium. Aug 2006.
  • 10. R. Penrose, Bull. Inst. Math. Appl. 10 (1974), 266.
  • 11. R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12 (1971), 177-209. MR 0297572 (45:6626)
  • 12. H. Wang, Proving theorems by pattern recognition-II, Bell System Tech. Journal, 40 (1961), 1-41.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 37B10, 37B50, 52C20, 37E15, 05B45, 52C23

Retrieve articles in all journals with MSC (2010): 37B10, 37B50, 52C20, 37E15, 05B45, 52C23


Additional Information

Wen-Guei Hu
Affiliation: Department of Applied Mathematics, National Chiao Tung University, Hsin-Chu 30010, Taiwan
Email: wwk.am94g@nctu.edu.tw

Song-Sun Lin
Affiliation: Department of Applied Mathematics, National Chiao Tung University, Hsin-Chu 30010, Taiwan
Email: sslin@math.nctu.edu.tw

DOI: https://doi.org/10.1090/S0002-9939-2010-10518-X
Received by editor(s): July 15, 2009
Received by editor(s) in revised form: March 29, 2010
Published electronically: August 6, 2010
Additional Notes: The authors would like to thank the National Science Council, R.O.C. (Contract No. NSC 95-2115-M-009) and the National Center for Theoretical Sciences for partially supporting this research.
Communicated by: Yingfei Yi
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society