Is every “even” polyomino with one hole tileable by dominoes

polyominotiling

In Conformal Invariance of Domino Tiling the author defines an even polyomino as a polyomino with all corners (of all borders, inside and outside) "black" if the polyomino is colored with the checkerboard coloring. A corner is black if the interior angle lies in a black square, like this:

enter image description here

Here are some examples:

enter image description here
enter image description here
enter image description here

My question is whether it is true that an even polyomino with one hole is always tileable by dominoes.

Background: A related polyomino is called a Temperleyan polyomino (in the same paper), which is formed from an even polyomino by removing one black corner from the outer border, and appending a black cell to each interior border. Here are some examples:

enter image description here
enter image description here

The paper shows (although not really in a way I can follow) Temperleyan polyomino are tileable by dominoes.

It is also easy to show that the deficiency (black minus white cells) in an even polyomino with $H$ holes is $1 – H$, so an even polyomino with 1 hole is balanced (has the same number of black and white cells).

The holes of even polyominoes are also even.

Best Answer

It is true! An even polyomino with one hole is tileable by dominoes.

The proof below has a few sketchy elements; a proof without those will be nice.

Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).

enter image description here

Here, tileable means tileable by dominoes.

  1. A ring is a polyomino where each cell has exactly two borders. All rings are tileable.

  2. A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.

An example of this manipulation:

enter image description here

  1. A $2 \times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.

An example of this manipulation:

enter image description here

  1. All convex corners of a even polyomino are one of these four types:

enter image description here

(This part is a bit sketchy; it requires considering many cases.)

  1. If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:

enter image description here

  1. A figure with only type 3 and 4 convex corners and one hole cannot contain a $2\times2$ subfigure.

Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2\times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2\times 2$ subfigure.

enter image description here

In this^ image, there is a $2 \times 2$ square, contained in a $3\times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.

  1. We cannot have any X or T junctions in a figure with no $2\times2$ subfigures, no peaks, and one hole.

Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.

Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.

  1. This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).

(This is also sketchy, and require cases to make sure we cannot have other possibilities.)

  1. This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2\times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.

Some remarks:

  • The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2\times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)

enter image description here

  • An algorithm follows immediately from the border manipulations.
Related Question