15
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ What prevents the 5 by 3 rectangle with a 2 by 1 hole in the centre from being a counterexample? All corner squares are black. but the number of squares is odd so it can't be tiled. $\endgroup$ – orlp Aug 1 '18 at 0:34
  • 1
    $\begingroup$ If you remove the "outer layer" (any cell with a corner touching the outside) from an even polyomino, do you get an even polyomino? And can the "outer layer" be tiled by dominoes (i.e. is it even length)? $\endgroup$ – Reinstate Monica Aug 1 '18 at 1:19
  • 1
    $\begingroup$ @Solomonoff'sSecret I found a proof today, and am busy typing it out. It relies basically on the idea you have. $\endgroup$ – Herman Tulleken Aug 1 '18 at 1:23
  • 1
    $\begingroup$ @HermanTulleken Yes, I strongly believe the answer to both my questions are "yes", from which the conclusion follows by induction. $\endgroup$ – Reinstate Monica Aug 1 '18 at 1:24
  • 1
    $\begingroup$ My proof is flawed and not easily fixed and yours takes a fundamentally more sound approach. $\endgroup$ – Reinstate Monica Aug 1 '18 at 2:02
3
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ Regarding step 4, what about + or T corners? $\endgroup$ – Reinstate Monica Aug 1 '18 at 2:01
  • $\begingroup$ Hmmmm yes this is a problem. Although it can be resolved I think. I will add those cases. (Lol maybe this proof is broken after all.) $\endgroup$ – Herman Tulleken Aug 1 '18 at 2:05
  • $\begingroup$ @Solomonoff'sSecret I edited and expanded the proof to address the issues you raised. (Note, the four corners of step 4 has been changed to 4 convex corners. and parts have been added to show these junctions cannot exist after we did all manipulations in 2 and 3.) $\endgroup$ – Herman Tulleken Aug 1 '18 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.