Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
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?)


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: http://dx.doi.org/10.1090/S0002-9939-2010-10518-X
PII: S 0002-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.