Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf

I could not reproduce theorem 5.7:

Every solvable set (tilable) has a solution S such that every finite block occurring in S also occurs infinitely often in S:

Proof in the text: Given a solution T and the set K of all finite blocks occurring in T, consider the set L of all subsets of K such that a subset A of K belongs to the L if there is a solution covered by A, i.e., in that solution all occurring finite blocks belong A. The set L is not empty because K belongs to it and it has minimal members. ...

Here's my problem: I could not see why the minimal member exists. There might be a sequence of A1>=A2>=A3>= ... belonging to L but their intersection does not belong to it ... I lacked a proof here... Any idea?

share|improve this question
3  
Wild guess: Zorn's lemma? (I haven't tried to read the paper.) –  Francois Ziegler May 28 at 4:26
1  
Not exactly - Konig's lemma: en.wikipedia.org/wiki/K%C3%B6nig%27s_lemma –  domotorp May 28 at 11:19

3 Answers 3

up vote 5 down vote accepted

Note that the set of solutions of a set $A$ is a closed set (with respect to the product topology): every tiling that is not a solution of $A$ has an occurrence of a finite pattern $p$ not in $A$, and the cylinder set around $p$ (the set of all tilings with pattern $p$ on the same position) is an open set consisting only of tilings that are not solutions of $A$.

Now, if you have a chain of sets $A_1\supseteq A_2\supseteq\cdots$ all with non-empty solution sets, their solution sets form a decreasing chain $X_1\supseteq X_2\supseteq \cdots$ of closed sets. Since the space is compact, the intersection $X_\infty:=\bigcap_i X_i$ is a non-empty closed set. Moreover, the intersection $X_\infty$ is precisely the set of solutions of $A_\infty:=\bigcap_i A_i$. Hence, $A_\infty$ is indeed in the partially ordered set $\mathcal{L}$.

Now you can apply Zorn's lemma.

share|improve this answer
    
It seems I lack some knowledge in the topological space of Wang Tile. I could not figure out why the set of solutions of a set A is could form a product topology... Could you provide with me some info? –  user40780 May 28 at 13:43
    
Sorry that i accidentally delete the comment.... how about the openness, closedness, and compactness, how do we prove them? I am actually trying to prove the compactness of the topological space (not yet the product topology)... –  user40780 May 28 at 15:11
1  
Consider your finite set of tiles $\Sigma$ with discrete topology. Then, the set of all possible tilings $\Sigma^{\mathbb{Z}^2}$ can be given the product topology. Since $\Sigma$ is finite, the discrete topology on it is compact, hence also the product topology on $\Sigma^{\mathbb{Z}^2}$. The cylinder sets are open and form a basis for the topology. From compactness it follows that cylinders are also closed. –  Algernon May 28 at 15:14
    
Thank you very much for your patience:) –  user40780 May 28 at 15:15
1  
I didn't get your last question. For the compactness of the product topology, take a sequence of tilings repeatedly choose subsequences that eventually agree on larger and larger regions around the origin. Then you get convergence for the diagonal subsequence. Alternatively, you can invoke Tychonoff's theorem. –  Algernon May 28 at 15:19

I didn't read it carefully, but it seems that one could build a minimal member from the bottom up. There is an infinite tiling $T$ (of the plane?) made up of $1 \times 1$ square tiles with colored edges. There is some finite number $N_1$ of (types of) $1 \times 1$ squares which occur in $T$. If possible reduce that set to a subset which is minimal in that it still allows some tiling (perhaps a different one) but any further reduction will not allow a tiling (if that is NOT possible then the set of $N_1$ types is already minimal). If this minimum set has $n_1$ types then it will have some number $N_2 \le n_1^4$ of $2 \times 2$ patches which occur. Similarly reduce this (if possible) to some smaller set of $2 \times 2$ patches which still permit a tiling (perhaps changing the tiling again). Now look at the $N_3 \le n_1^9$ $3 \times 3$ patches which occur in the latest tiling and reduce it if possible. Continue in this manner for all finite sizes $%k \times k.$ The end result is some minimal (but infinite) set of finite square patches which allows one or more tilings but fails to do so if even one further patch is forbidden.

share|improve this answer
    
So the problem I have is: why would I have an end result instead of that the solution just keeps changing? –  user40780 May 28 at 13:08
1  
the 1x1 terminates and never changes after that then the 2x2 terminates and stays the same then the 3x3 terminates etc. At each stage what you are left with may be less than before but still supports a tiling. So the intersection of all the steps is not empty. –  Aaron Meyerowitz May 28 at 22:02

Since I know nothing about Wang tiles, my notation and terminology are probably bad. I hope my argument is correct.

Let $W$ be a solvable finite set of Wang tiles.

A set $\mathcal A$ of finite blocks is avoidable (with respect to the fixet set $W$ of Wang tiles) if there is a ($W$-)tiling of the plane in which no element of $\mathcal A$ occurs.

$\emptyset$ is avoidable, since $W$ is solvable.

A set $\mathcal A$ is avoidable if and only if every finite subset of $\mathcal A$ is avoidable.

Proof. For the nontrivial direction, suppose every finite subset of $\mathcal A$ is avoidable. Since $W$ is finite, $W^{\mathbb Z\times\mathbb Z}$ is a compact space. ($W$ has the discrete topology, $W^{\mathbb Z\times\mathbb Z}$ the Tychonoff product topology.) $F_0=\{T\in W^{\mathbb Z\times\mathbb Z}:T\text{ is a proper tiling }\}$ is a closed set, as is $F_A=\{T\in W^{\mathbb Z\times\mathbb Z}:A\text{ does not occur in }T\}$ for each $A\in\mathcal A$. Since the family $\{F_0\}\cup\{F_A:A\in\mathcal A\}$ has the finite intersection property, it has nonempty intersection; i.e., $\mathcal A$ is avoidable.

Hence there is a maximal avoidable set of finite blocks, choose one and call it $\mathcal A$.

Let $S$ be a tiling of the plane in which no element of $\mathcal A$ occurs. I claim that every finite block occurring in $S$ occurs infinitely often. Assume for a contradiction that some finite block $B$ occurs at least once in $S$ but occurs only a finite number of times. Then $S$ contains arbitrarily large squares in which $B$ does not occur at all, i.e., arbitrarily large squares can be tiled with no occurrence of any element of $\mathcal A\cup B$. Now another easy application of compactness shows that the whole plane can be tiled with no occurrence of any element of $\mathcal A\cup\{B\}$; that is, the set $\mathcal A\cup\{B\}$ is avoidable. But $B\notin\mathcal A$ (since $B$ occurs in $S$), so this contradicts the maximality of $\mathcal A$.

I guess this is the same idea as Aaron Meyerowitz's answer but more verbose. Well, maybe somebody will find a verbose answer easier to follow.

P.S. If your background is engineering and physics, you may not like my use of topological compactness. You can give an equivalent proof using König's infinity lemma, that a finitely-branching infinite tree has an infinite branch.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.