Nonemptiness problems of plane square tiling with two colors
HTML articles powered by AMS MathViewer
- by Wen-Guei Hu and Song-Sun Lin PDF
- Proc. Amer. Math. Soc. 139 (2011), 1045-1059 Request permission
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
- Jung-Chao Ban and Song-Sun Lin, Patterns generation and transition matrices in multi-dimensional lattice models, Discrete Contin. Dyn. Syst. 13 (2005), no. 3, 637–658. MR 2152335, DOI 10.3934/dcds.2005.13.637
- J.C. Ban, W.G. Hu, S.S. Lin and Y.H. Lin, Zeta functions for two-dimensional shifts of finite type, preprint (2008).
- Jung-Chao Ban, Song-Sun Lin, and Yin-Heng Lin, Patterns generation and spatial entropy in two-dimensional lattice models, Asian J. Math. 11 (2007), no. 3, 497–534. MR 2372728, DOI 10.4310/AJM.2007.v11.n3.a7
- Robert Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. 66 (1966), 72. MR 216954
- Karel Culik II, An aperiodic set of $13$ Wang tiles, Discrete Math. 160 (1996), no. 1-3, 245–251. MR 1417576, DOI 10.1016/S0012-365X(96)00118-5
- Branko Grünbaum and G. C. Shephard, Tilings and patterns, A Series of Books in the Mathematical Sciences, W. H. Freeman and Company, New York, 1989. An introduction. MR 992195
- Jarkko Kari, A small aperiodic set of Wang tiles, Discrete Math. 160 (1996), no. 1-3, 259–264. MR 1417578, DOI 10.1016/0012-365X(95)00120-L
- A. Lagae and P. Dutré, An alternative for Wang tiles: Colored edges versus colored corners, ACM Trans. Graphics, 25 (2006), no. 4, 1442–1459.
- 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.
- R. Penrose, Bull. Inst. Math. Appl. 10 (1974), 266.
- Raphael M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177–209. MR 297572, DOI 10.1007/BF01418780
- H. Wang, Proving theorems by pattern recognition-II, Bell System Tech. Journal, 40 (1961), 1–41.
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
- 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
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2745655