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 be the following chessboard
and let denote the set of the “true” dominoes of size 2, that is
Is it possible to tile using only ? Surprisingly, this problem can be solved thanks to the van Kampen diagrams used in group theory.
Let be a group presentation. A van Kampen diagram , relative to , is a finite connected planar graph whose edges are oriented and labelled by the generators , such that the word labelling the boundary of any cell of (ie., any bounded component of ) is a relator . For convenience, we call the word labelling the boundary of the unbounded component of the boundary word of .
For example, if we consider the presentation , the following graph defines a van Kampen diagram (relative to ) whose boundary word is .
Theorem 1: Let be a group with a presentation . A given word written over is equal to in if and only there exists a van Kampen diagram , relative to , whose boundary word is .
Proof. Suppose that there exists a van Kampen diagram whose boundary word is . We easily prove that in by induction on the number of cells of . If has just one cell, then its boundary word is a relator of by definition, so that that trivially. If has at least two cells, then we can write where corresponds to the intersection between the boundary path of and the boundary of one of its cells . Let be the relator associated to . Removing to , we obtain a new van Kampen diagram whose boundary word is . By our induction hypothesis, we conclude that
in our group .
Conversely, suppose that in . Thus, as an element of the free group , the word belongs to the normal subgroup generated by , so we can write
for some and . Now consider the following van Kampen diagram:
Clearly, it defines a van Kampen diagram whose boundary word is .
Now, we associate a group presentation to any set of dominoes . Let be two fixed letters. To any dominoe , we define a word written over following the rule illustrated by
Let denote the group presentation and the underlying group. For example,
with the notation . Now, we can notice that a tiling of some chessboard using produces a van Kampen diagram relative to . For example, the tiling
of using 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 , then its boundary word is equal to in the group .
As a concrete application, we are now able to solve our initial problem:
Theorem 3: can be tiled by if and only if and don’t have the same parity.
Proof. As we already noticed,
The boundary path of is
Notice that and belongs to the center of . Thus, if and are both odd,
and if they are both even,
Now we want to prove that and in . For this purpose, let us consider the morphism
onto the infinite dihedral group . It is clear that and
in . Therefore, these words are not equal to in as well. According to Theorem 2, we conclude that cannot be tiled by if and have the same parity.
Conversely, suppose without loss of generality that is even and odd. Now, the particular tiling
clearly yields a tiling of by .
In fact, Theorem 3 can be deduced from the following tricky argument: First, it is obvious that if can be tiled by then must have an odd number of squares. Thus, if and are both odd, cannot be tiled by . Secondly, if we color the squares of in black and white exactly as a true chessboard and if are both even, then is obtained from a chessboard by removing two squares of the same color, say two black squares. But, if we color the dominoes of so that they contain a square of each color, we deduce that, if could be tiled by , it would contain the same number of black and white squares. Therefore, we conclude that cannot be tiled by if and are both even.
In the same way, if we denote by the chessboard
then we can prove:
Theorem 4: can be tiled by if and only if or 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 denote the following set of dominoes:
Then, the associated group presentation is
Following the proof of Theorem 3, we get:
Theorem 5: can be tiled by if and only if .
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.