Nonemptiness problems of plane square tiling with two colors
Wen-Guei Hu, Song-Sun Lin · Proceedings of the American Mathematical Society · 2010
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}) eq \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}) eq \emptyset$, then $\mathcal {B}$ has a subset $\mathcal {B}’$ of minimal cycle generator such that $\mathcal {P}(\mathcal {B}’) eq \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}}) eq \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}) eq \emptyset$, then $\mathcal {P}(\mathcal {B}) eq \emptyset$. The problem is decidable for $p=2$: $\Sigma (\mathcal {B}) eq \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.