32
$\begingroup$

The tiling world is a bit aflutter recently with the drop of Smith, Meyers, Kaplan, and Goodman-Strauss's paper showing an einstein - a simply-connected polygon - that must aperiodically tile the plane. Their einstein is a concave 13-gon that they have called the "hat" monotile.

Image from Smith et al.

The figures in the paper show how the tiling is manifestly aperiodic - the image above is from Kaplan's tweet announcing the paper.

Earlier I think in "Mathematical Games" in a Scientific American article from the '70s, Martin Gardner relayed a question from John Conway about whether a (rhombic) Penrose tiling of the plane could admit a three-coloring; this was algorithmically answered in the affirmative by Sibley and Wagon. I dug up some plastic Penrose rhombi that I had bought about 25 years ago, and indeed they came in only three colors. It's a (straightforward but fun) puzzle to tile with only these three colors.

The same question can be asked about the SMKG einstein - can we three-color any tiling with the above 13-gon monotile? If so, can we give an efficient algorithm?

The construction is gloriously simple and could be taught to bright young children. How many colors would be needed to 3D-print a bunch of these?

Added later

As we know, four colors suffice, but some questions may remain about how easy it is to four-color the monotiling. Jesse Clark suggested that it could be easily four-colored along radial stripes here.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Squares can aperiodically tile the plane, so a tile that can aperiodically tile is no big deal. The point has been to find a polygon that can only tile aperiodically. $\endgroup$
    – Gerry Myerson
    Mar 21 at 22:08
  • 1
    $\begingroup$ Older question about aperiodic monotiles: (non-)existence of the aperiodic monotile $\endgroup$
    – Gerry Myerson
    Mar 21 at 22:13
  • 3
    $\begingroup$ @GerryMyerson Traditionally, there is a distinction between the terms aperiodic and non-periodic. A tiling is non-periodic if it is not periodic. A set of tiles is aperiodic if it tiles the plane, but every tiling is non-periodic. This terminology may not be universal but it is pretty common. $\endgroup$
    – Timothy Chow
    Mar 22 at 22:50
  • 1
    $\begingroup$ The four-coloring question has now been raised at How can one construct a four-coloring of a tiling of the plane with Smith, Meyers, Kaplan, and Goodman-Strauss's aperiodic monotile? $\endgroup$
    – Gerry Myerson
    Mar 25 at 4:36
  • $\begingroup$ I'll edit the question a bit later on when it's not so busy but further to this YouTube video presentation by some of the authors, the tile was initially discovered in the fall of '22 and was suspected of being aperiodic; this was proved with a computer-assisted proof and also a separate 'human-readable' manner by early '23 - the proof techniques are quite sophisticated and far from obvious. $\endgroup$
    – Mark S
    Mar 26 at 22:34

1 Answer 1

Reset to default
31
$\begingroup$

No, you cannot three-color that tiling.

Here's a finite part of the tiling from page 10 top left of the article, the tile numbered 2 here is the one darkened on that figure. This part cannot be three-colored.

To prove this, start from the three adjacent tiles marked 0, 1, 2, and call their colors yellow, blue and red respectively. Tile 0 is surrounded by a sequence of adjacent tiles 1, 2, 3, 4, 5, 6, so these must be colored blue and red alternatingly, 5 being blue, 6 being red. Tile 7 is adjacent to tile 5 and 6 and so must be yellow; while tile 8 is adjacent to tile 1 and 6 and so also must be yellow. Now tile 9 is adjacent to tiles 6 and 8 and so must be blue, but tile 10 is adjacent to 6 and 7 and so also must be blue, but 9 and 10 are adjacent so this coloring is invalid.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Nice! And a little surprising. $\endgroup$
    – Mark S
    Mar 22 at 3:13
  • 2
    $\begingroup$ Is it possible that there is some other (necessarily also aperiodic) tiling of the plane by this tile that is three colourable? Or must every such tiling contain the above configuration? $\endgroup$
    – Oscar Cunningham
    Mar 22 at 16:50
  • 2
    $\begingroup$ @OscarCunningham I don't know. I suspect that the configuration must always appear, but mostly by analogy with Penrose tilings, and I don't know enough about this new result to know whether that applies here. $\endgroup$
    – Zsbán Ambrus
    Mar 22 at 18:27
  • 7
    $\begingroup$ @ZsbánAmbrus I asked this on Mastodon. It seems that every tiling does contain this configuration: mathstodon.xyz/@OscarCunningham/110064573096081586. $\endgroup$
    – Oscar Cunningham
    Mar 23 at 5:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .