二維邊著色及三維面著色在非空問題之研究

Abstract

本論文探討在二維邊著色及三維面著色之非空問題。在平面的 邊著色(Wang tiles)問題上,我們允許兩個邊著色正方形相連若 其相連時共用的邊具有相同的顏色。 給定一個 Wang tiles 的子集合 B,非空問題是探討是否存在由 B 組成的全平面花樣。王浩院士提出了一個二維邊著色非空問題之 猜想:若 B 存在全平面花樣之拼法,則必存在由 B 組成的週期性花 樣拼法。當邊著色的顏色數為五,已證明此猜測是錯誤的。當顏色 數為二,此猜測為正確的。在第二節中,我們證明了當顏色數為 3 時,此猜測也是正確的。 同理我們可將二維推廣至三維:面著色之單位立方體稱為 Wang cubes。在三維時,我們允許兩個面著色單位立方體相連若其相連時 共用的面具有相同的顏色。在第三節中,我們證明了在三維面著色 且顏色數為 2 的非空問題上,王浩的猜測也是正確的。

In this dissertation, we consider the nonemptiness problems of Wang tiles with three colors and Wang cubes with two colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not Σ(B) ≠ ∅, where Σ(B) is the set of all global patterns on Z2 that can be constructed from the Wang tiles in B. Wang’s conjecture is that for any B of Wang tiles, Σ(B) ≠ ∅ if and only if P(B) ≠ ∅, where P(B) is the set of all periodic patterns on Z2 that can be generated by the tiles in B. When p ≥ 5, Wang’s conjecture is known to be wrong. When p = 2, the conjecture is true. In section 2, we prove that when p = 3, the conjecture is also true. Similarly, Wang cubes are unit cubes with colored faces, which generalized from Wang tiles. In the face coloring of a space, Wang cubes stack the whole space such that the touching faces of adjacent cubes have the same colors. For Wang cubes, the corresponding Wang conjecture is that if Σ(B) ≠ ∅, then P(B) ≠ ∅. In section 3, we prove that Wang conjecture holds on face coloring when p = 2.