<p>Yes, this is a compactness property.</p>

<p>Let <span class="math-container">$X$</span> be the region you want to tile, and <span class="math-container">$T$</span> the finite set of possible tiles. The space <span class="math-container">$T^X$</span> of all assignments of tiles to <span class="math-container">$X$</span> is compact by Tychonoff’s theorem. For any finite <span class="math-container">$X_0\subseteq X$</span>, the set <span class="math-container">$C_{X_0}\subseteq T^X$</span> of all correct tilings of <span class="math-container">$X_0$</span> is closed (in fact, clopen), and since <span class="math-container">$C_{X_0\cup X_1}\subseteq C_{X_0}\cap C_{X_1}$</span>, they generate a filter. Thus, assuming every finite subset of <span class="math-container">$X$</span> can be tiled, the system <span class="math-container">$\{C_{X_0}:X_0\subseteq X\text{ finite}\}$</span> has fip, and by compacteness, its intersection is nonempty. This intersection is the set of all correct tilings of <span class="math-container">$X$</span>.</p>

<p>Instead of all finite <span class="math-container">$X_0$</span>, it suffices to use any family of finite subsets which is upwards directed and covers <span class="math-container">$X$</span>, such as, in your case, the set of all finite square subregions of the plane.</p>

<p>Alternatively, you may set up the argument to use the compacteness of classical propositional logic: let <span class="math-container">$\{p_{x,t}:x\in X,t\in T\}$</span> be a set of propositional variables, and let <span class="math-container">$C$</span> be the theory consisting of the formulas
<span class="math-container">$$\begin{gather*}
\bigvee_{t\in T}p_{x,t},\qquad x\in X,\\
\neg(p_{x,t}\land p_{x,t'}),\qquad x\in X,t\ne t'\in T,
\end{gather*}$$</span>
and
<span class="math-container">$$\neg(p_{x,t}\land p_{x',t'})$$</span>
for all <span class="math-container">$x,x'\in X$</span> that are neighbours, and <span class="math-container">$t,t'\in T$</span> that are incompatible when placed on <span class="math-container">$x$</span> and <span class="math-container">$x'$</span>, respectively. If each finite subset of <span class="math-container">$X$</span>can be tiled, then <span class="math-container">$C$</span> is consistent, and any satisfying assignment gives a tiling of <span class="math-container">$X$</span>.</p>

CC BY-SA 4.0
2019-04-01T07:23:41.383Z
Yes, I thought about an argument using compactness of propositional logic. Yet this argument is in a sense not constructive because implicitly uses the Axiom of Chioce and hides an algorithmic property that should sound as follows: if $t_1: X \to T $ is a tiling and $t_2: Y \to T$ is another one whose with $Y\supseteq X$, then there exists a finite sequence of transformations of $t_2$ yielding a $t_3: Y \to T$ that extends $t_1$. Something similar is detailed in this answer https://math.stackexchange.com/a/36109/34750 but concerns other domini pieces rather than Wang tiles.
Alberto
CC BY-SA 4.0
2019-04-01T06:42:21.990Z
2019-04-01T06:59:21.283Z
2019-04-01T06:59:21.283Z
Emil Jeřábek
<p>First, there is an infinite tiling of the plane if and only if there are square tilings 
<span class="math-container">$$
T_1 &lt; T_2 &lt; T_3 &lt; \ ...
$$</span>
such that <span class="math-container">$T_i$</span> is an <span class="math-container">$i \times i$</span> square tiling, and <span class="math-container">$T_i$</span> is a subtiling of <span class="math-container">$T_{i+1}$</span>. </p>

<p>Now, for each <span class="math-container">$T_i$</span> define <span class="math-container">$f(T_i)$</span> to be the size of the largest square tiling that <span class="math-container">$T_i$</span> is a subtiling of, where <span class="math-container">$f(T_i) = \infty$</span> if for all <span class="math-container">$n &gt; i$</span>, <span class="math-container">$T_i$</span> is a subtiling of some <span class="math-container">$n\times n$</span> tiling.</p>

<p>Lemma 1: if for an <span class="math-container">$i \times i$</span> tiling <span class="math-container">$T_i$</span>, <span class="math-container">$f(T_i) = \infty$</span>, then there is some <span class="math-container">$(i+1) \times (i+1)$</span> tiling <span class="math-container">$T_{i+1}$</span> with <span class="math-container">$T_i &lt; T_{i+1}$</span> and <span class="math-container">$f(T_{i+1}) = \infty$</span>.</p>

<p>Proof: Suppose not. Then look at the maximum value <span class="math-container">$n$</span> of <span class="math-container">$f(T)$</span> for <span class="math-container">$(i+1) \times (i+1)$</span> tilings containing <span class="math-container">$T_i$</span>:</p>

<p><span class="math-container">$$n = \max_{T &gt; T_i \atop T \mathrm{\ is\ } (i+1) \times (i+1)} f(T). $$</span></p>

<p>If this is finite, then no tiling containing <span class="math-container">$T_i$</span> can be larger than <span class="math-container">$n \times n$</span>, contradicting <span class="math-container">$f(T_i) = \infty$</span>. And if it is infinite, one of the <span class="math-container">$(i +1) \times (i+1)$</span> tilings <span class="math-container">$T$</span> must have <span class="math-container">$f(T) = \infty$</span>, as otherwise we have <span class="math-container">$\infty$</span> is the maximum of a finite number of finite integers (since there are a finite number of <span class="math-container">$(i+1) \times (i+1)$</span> tilings).</p>

<p>So at least one of the <span class="math-container">$(i+1) \times (i+1)$</span> tilings containing <span class="math-container">$T$</span> must have an infinite value for <span class="math-container">$f$</span>. QED</p>

<p>Now, we can ask whether <span class="math-container">$f(T_1) = \infty$</span> for any single <span class="math-container">$1 \times 1$</span> tile. 
If not, then there is a maximum size square that admits a tiling. And if so, then given a tiling <span class="math-container">$T_1$</span> with <span class="math-container">$f(T_1) = \infty$</span>, we can use lemma 1 to find tilings 
<span class="math-container">$$
T_1 &lt; T_2 &lt; T_3 &lt; \ ...
$$</span>
such that <span class="math-container">$f(T_i) = \infty$</span> for all <span class="math-container">$i$</span>, 
showing that there is an infinite tiling of the plain.</p>

CC BY-SA 4.0
2019-04-01T01:56:34.107Z
2019-04-01T01:56:34.107Z
Peter Shor 
<p>I've read in Lemma 2 of the paper <a href="https://arxiv.org/abs/1506.06492" rel="nofollow noreferrer" title="An aperiodic tileset of 11 Wang tiles">1</a> that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted.  This sounds like a compactness property, but I don't see how easy can be proven.</p>

<p>I added the tag "automata theory" because there is a correspondence between Wang tilings and finite state transducers.</p>

<co.combinatorics><lo.logic><computability><automata-theory>
Compactness of domino tilings
Alberto
# Compactness of domino tilings

(Asked by: username_0 on 2019-03-31)

I've read in Lemma 2 of the paper [1](https://arxiv.org/abs/1506.06492 "An aperiodic tileset of 11 Wang tiles") that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted. This sounds like a compactness property, but I don't see how easy can be proven.

I added the tag "automata theory" because there is a correspondence between Wang tilings and finite state transducers.

**Tags:** co.combinatorics, lo.logic, computability, automata-theory

---

## 2 answers

### Answer by username_1 on 2019-04-01. Score: 5 | Accepted answer

Yes, this is a compactness property.

Let $X$ be the region you want to tile, and $T$ the finite set of possible tiles. The space $T^X$ of all assignments of tiles to $X$ is compact by Tychonoff’s theorem. For any finite $X\_0\subseteq X$, the set $C\_{X\_0}\subseteq T^X$ of all correct tilings of $X\_0$ is closed (in fact, clopen), and since $C\_{X\_0\cup X\_1}\subseteq C\_{X\_0}\cap C\_{X\_1}$, they generate a filter. Thus, assuming every finite subset of $X$ can be tiled, the system $\{C\_{X\_0}:X\_0\subseteq X\text{ finite}\}$ has fip, and by compacteness, its intersection is nonempty. This intersection is the set of all correct tilings of $X$.

Instead of all finite $X\_0$, it suffices to use any family of finite subsets which is upwards directed and covers $X$, such as, in your case, the set of all finite square subregions of the plane.

Alternatively, you may set up the argument to use the compacteness of classical propositional logic: let $\{p\_{x,t}:x\in X,t\in T\}$ be a set of propositional variables, and let $C$ be the theory consisting of the formulas
$$\begin{gather\*}
\bigvee\_{t\in T}p\_{x,t},\qquad x\in X,\\
\neg(p\_{x,t}\land p\_{x,t'}),\qquad x\in X,t\ne t'\in T,
\end{gather\*}$$
and
$$\neg(p\_{x,t}\land p\_{x',t'})$$
for all $x,x'\in X$ that are neighbours, and $t,t'\in T$ that are incompatible when placed on $x$ and $x'$, respectively. If each finite subset of $X$can be tiled, then $C$ is consistent, and any satisfying assignment gives a tiling of $X$.

> **Comments:**
> **username_0**: Yes, I thought about an argument using compactness of propositional logic. Yet this argument is in a sense not constructive because implicitly uses the Axiom of Chioce and hides an algorithmic property that should sound as follows: if $t_1: X \to T $ is a tiling and $t_2: Y \to T$ is another one whose with $Y\supseteq X$, then there exists a finite sequence of transformations of $t_2$ yielding a $t_3: Y \to T$ that extends $t_1$. Something similar is detailed in this answer https://math.stackexchange.com/a/36109/34750 but concerns other domini pieces rather than Wang tiles.  

---

### Answer by username_2 on 2019-04-01. Score: 2

First, there is an infinite tiling of the plane if and only if there are square tilings
$$
T\_1 < T\_2 < T\_3 < \ ...
$$
such that $T\_i$ is an $i \times i$ square tiling, and $T\_i$ is a subtiling of $T\_{i+1}$.

Now, for each $T\_i$ define $f(T\_i)$ to be the size of the largest square tiling that $T\_i$ is a subtiling of, where $f(T\_i) = \infty$ if for all $n > i$, $T\_i$ is a subtiling of some $n\times n$ tiling.

Lemma 1: if for an $i \times i$ tiling $T\_i$, $f(T\_i) = \infty$, then there is some $(i+1) \times (i+1)$ tiling $T\_{i+1}$ with $T\_i < T\_{i+1}$ and $f(T\_{i+1}) = \infty$.

Proof: Suppose not. Then look at the maximum value $n$ of $f(T)$ for $(i+1) \times (i+1)$ tilings containing $T\_i$:

$$n = \max\_{T > T\_i \atop T \mathrm{\ is\ } (i+1) \times (i+1)} f(T). $$

If this is finite, then no tiling containing $T\_i$ can be larger than $n \times n$, contradicting $f(T\_i) = \infty$. And if it is infinite, one of the $(i +1) \times (i+1)$ tilings $T$ must have $f(T) = \infty$, as otherwise we have $\infty$ is the maximum of a finite number of finite integers (since there are a finite number of $(i+1) \times (i+1)$ tilings).

So at least one of the $(i+1) \times (i+1)$ tilings containing $T$ must have an infinite value for $f$. QED

Now, we can ask whether $f(T\_1) = \infty$ for any single $1 \times 1$ tile.
If not, then there is a maximum size square that admits a tiling. And if so, then given a tiling $T\_1$ with $f(T\_1) = \infty$, we can use lemma 1 to find tilings
$$
T\_1 < T\_2 < T\_3 < \ ...
$$
such that $f(T\_i) = \infty$ for all $i$,
showing that there is an infinite tiling of the plain.


---

