In this note, we are interested in the following problem: given a chessboard and a set of dominoes, is it possible to tile our chessboard using the dominoes we have? For example, let $C(m,n)$ be the following chessboard

and let $D_2$ denote the set of the “true” dominoes of size 2, that is

Is it possible to tile $C(m,n)$ using only $D_2$? Surprisingly, this problem can be solved thanks to the van Kampen diagrams used in group theory.

Let $\Pi = \langle g_1,\ldots, g_n \mid r_1= \cdots = r_m=1 \rangle$ be a group presentation. A van Kampen diagram $\Gamma \subset \mathbb{R}^2$, relative to $\Pi$, is a finite connected planar graph whose edges are oriented and labelled by the generators $g_1, \ldots, g_n$, such that the word labelling the boundary of any cell of $\Gamma$ (ie., any bounded component of $\mathbb{R}^2 \backslash \Gamma$) is a relator $r_1, \ldots, r_m$. For convenience, we call the word labelling the boundary of the unbounded component of $\mathbb{R}^2 \backslash \Gamma$ the boundary word of $\Gamma$.

For example, if we consider the presentation $\Pi = \langle x,y \mid x^2=y^2, \ y=xyx \rangle$, the following graph defines a van Kampen diagram (relative to $\Pi$) whose boundary word is $x^4$.

Theorem 1: Let $G$ be a group with a presentation $\Pi = \langle \Sigma \mid \mathcal{R} \rangle$. A given word $w$ written over $\Sigma$ is equal to $1$ in $G$ if and only there exists a van Kampen diagram $\Gamma$, relative to $\Pi$, whose boundary word is $w$.

Proof. Suppose that there exists a van Kampen diagram $\Gamma$ whose boundary word is $w$. We easily prove that $w=1$ in $G$ by induction on the number of cells of $\Gamma$. If $\Gamma$ has just one cell, then its boundary word is a relator of $\Pi$ by definition, so that that $w=1$ trivially. If $\Gamma$ has at least two cells, then we can write $w=uv$ where $u$ corresponds to the intersection between the boundary path of $\Gamma$ and the boundary of one of its cells $c$. Let $uz=1$ be the relator associated to $c$. Removing $c$ to $\Gamma$, we obtain a new van Kampen diagram whose boundary word is $z^{-1}v$. By our induction hypothesis, we conclude that

$w=uv=z^{-1}v=1$

in our group $G$.

Conversely, suppose that $w=1$ in $G$. Thus, as an element of the free group $F(\Sigma)$, the word $w$ belongs to the normal subgroup generated by $\mathcal{R}$, so we can write

$w = g_1r_1^{\pm 1} g_1^{-1} \cdot g_2r_2^{\pm 1} g_2^{-1} \cdots g_k r_k^{\pm 1} g_k^{-1}$

for some $r_j \in \mathcal{R}$ and $g_j \in F(\Sigma)$. Now consider the following van Kampen diagram:

Clearly, it defines a van Kampen diagram whose boundary word is $w$. $\square$

Now, we associate a group presentation to any set of dominoes $D$. Let $x,y$ be two fixed letters. To any dominoe $d \in D$, we define a word $w(d)$ written over $\{ x^{\pm 1}, y^{\pm 1} \}$ following the rule illustrated by

Let $\Pi(D)$ denote the group presentation $\langle x,y \mid w(d)=1, d \in D \rangle$ and $G(D)$ the underlying group. For example,

$\Pi(D_2)= \langle x,y \mid [x,y^2]=[y,x^2]=1 \rangle$

with the notation $[a,b]=aba^{-1}b^{-1}$. Now, we can notice that a tiling of some chessboard using $D$ produces a van Kampen diagram relative to $\Pi(D)$. For example, the tiling

of $C(5,2)$ using $D_2$ produces the van Kampen diagram

Thus, if we defined the boundary word of a chessboard as the word obtained by following the same rule as the one used for the dominoes, we deduce from Theorem 1:

Theorem 2: If a chessboard can be tiled by a set of dominoes $D$, then its boundary word is equal to $1$ in the group $G(D)$.

As a concrete application, we are now able to solve our initial problem:

Theorem 3: $C(m,n)$ can be tiled by $D_2$ if and only if $m$ and $n$ don’t have the same parity.

$\Pi(D_2)= \langle x,y \mid [x,y^2]=[x^2,y]=1 \rangle$.

The boundary path of $C(m,n)$ is

$w(m,n) = y^{n-1}xyx^{m-1}y^{-n+1}x^{-1}y^{-1}x^{-m+1}$.

Notice that $x^2$ and $y^2$ belongs to the center of $G(D_2)$. Thus, if $m$ and $n$ are both odd,

$w(m,n)= xyx^{-1}y^{-1}=[x,y]$,

and if they are both even,

$w(m,n)=y^{-1}xyx^{-1}yx^{-1}y^{-1}x=[y^{-1},x][y,x^{-1}]$.

Now we want to prove that $[x,y] \neq 1$ and $[y^{-1},x][y,x^{-1}] \neq 1$ in $G(D_2)$. For this purpose, let us consider the morphism

$\varphi : G(D_2) \twoheadrightarrow \langle x,y \mid x^2=y^2=1 \rangle$

onto the infinite dihedral group $D_{\infty}$. It is clear that $[x,y] \neq 1$ and

$[y^{-1},x][y,x^{-1}]=(yx)^4 \neq 1$

in $D_{\infty}$. Therefore, these words are not equal to $1$ in $G(D_2)$ as well. According to Theorem 2, we conclude that $C(m,n)$ cannot be tiled by $D_2$ if $m$ and $n$ have the same parity.

Conversely, suppose without loss of generality that $m$ is even and $n$ odd. Now, the particular tiling

clearly yields a tiling of $C(m,n)$ by $D_2$. $\square$

In fact, Theorem 3 can be deduced from the following tricky argument: First, it is obvious that if $C(m,n)$ can be tiled by $D_2$ then $C(m,n)$ must have an odd number of squares. Thus, if $m$ and $n$ are both odd, $C(m,n)$ cannot be tiled by $D_2$. Secondly, if we color the squares of $C(m,n)$ in black and white exactly as a true chessboard and if $m,n$ are both even, then $C(m,n)$ is obtained from a $m \times n$ chessboard by removing two squares of the same color, say two black squares. But, if we color the dominoes of $D_2$ so that they contain a square of each color, we deduce that, if $C(m,n)$ could be tiled by $D_2$, it would contain the same number of black and white squares. Therefore, we conclude that $C(m,n)$ cannot be tiled by $D_2$ if $m$ and $n$ are both even.

In the same way, if we denote by $K(m,n)$ the chessboard

then we can prove:

Theorem 4: $K(m,n)$ can be tiled by $D_2$ if and only if $m$ or $n$ is odd.

However, the argument using van Kampen diagrams can be adapted successfully to other tiling problems, where our previous trick does not work any more. Let $D_3$ denote the following set of dominoes:

Then, the associated group presentation is

$\Pi (D_3) = \langle x,y \mid [x,y^3]=[x^3,y]=1 \rangle$.

Following the proof of Theorem 3, we get:

Theorem 5: $K(m,n)$ can be tiled by $D_3$ if and only if $m=n=2 \ \text{mod} \ 3$.

The proof is left as an exercice.

This point of view was introduced by Conway and Lagarias, in their article Tiling with polyominoes and combinatorial group theory, and was also exploited by Thurston in Conway’s tiling groups. See also Hitchman’s article, The topology of tile invariants, and references therein for more information.