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

C(m,n)

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

D_2

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.

vanKampen

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:

vanKampen - proof

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

Rule

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

C(5,2) - Tiling

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

C(5,2) - vanKampen

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.

Proof. As we already noticed,

\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

C(6,5)

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

K(m,n)

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:

D_3

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.

 

Advertisements