14
$\begingroup$

This is motivated by the new paper of Smith, Myers, Kaplan, and Goodman-Strauss, wherein they define the existence of an aperiodic monotile. Clearly their tiling is not three-colorable, so we have from Appel and Haken (1977) that its chromatic number is 4. What is not clear to me, however, is how one could algorithmically construct such a coloring. Any suggestions would be much appreciated!

$\endgroup$
2

5 Answers 5

17
$\begingroup$

I tried to find a colouring where one of the colours comprised exactly the 'flipped' tiles. So I coloured all of the flipped tiles blue and then found three of the remaining tiles which were all touching and coloured them red, yellow and green arbitrarily. After this I found that I could keep expanding the colouring by finding an uncoloured tile that was touching two of red, yellow and green, and colouring it with the third colour. I never had to make any choices, so it seems that there is a unique colouring such that one of the colours comprises exactly the flipped tiles.

If this is true then the colouring is trivial to perform algorithmically, but I don't yet have a complete proof.

The 'hat' aperiodic monotiling. Each tile is coloured red, yellow, green or blue such that no adjacenta tiles have the same colour. Furthermore, the blue tiles are precisely the 'flipped' ones with the rarer orientation.


Look at the reduction to an hexagonal grid shown in Figure 2.2 of the original paper.

Merging each flipped tile with one of its neighbours yields a grid equivalent to the hexagonal grid. (Ignore the colouring here.)

The hexagonal grid is formed by merging each flipped tile with a neighbour. The hexagonal grid is strictly more connected than the unflipped tiles (i.e. there are hexagons that touch even though their corresponding tiles don't). So the unique 3-colouring of the hexagonal grid does indeed yield a 4-colouring of the original tiling.

It remains to show that this colouring is the unique such.


Added 2023-06-14: The new Spectre tiling does not involve any flipped tiles. However we can still produce a similar colouring. Some of the tiles are special in that their rotation is an odd multiple of $2\pi/12$ relative to the others. Colouring these tiles in blue, the remainder can again be three coloured in a unique way.

Such a colouring

$\endgroup$
4
  • 2
    $\begingroup$ Jesse Clark has the same colouring here: twitter.com/myhf/status/1639053012399439872. They didn't notice that the flipped tiles are all the same colour, but did point out that four tiles meeting at a point all have different colours. $\endgroup$ Commented Mar 25, 2023 at 9:16
  • $\begingroup$ Nice! Is there a wallpaper group hiding in the first image? $\endgroup$
    – Mark S
    Commented Mar 25, 2023 at 13:30
  • 1
    $\begingroup$ @MarkS If you squint a bit, you can see that the red, yellow and green tiles form hexagonal grids with the same angle and spacing, while the blue tiles form a hexagonal grid with a different angle and larger spacing. My guess would be that the constants relating the two grids are irrational, killing any wallpaper group. $\endgroup$ Commented Mar 25, 2023 at 15:59
  • $\begingroup$ I think it is worth to point out that the "special" tiles in Spectre tiling are not arbitrary -- in the Hat tiling, you can smoothly change a parameter to get a spectrum of aperiodic tiles; Hat and Turtle are popular ones, and Spectre is one of the shapes in this spectrum (which happens to admit different tilings if mirroring is allowed). The same operation can be done with Spectre tiling, but (except the Spectre parameter) you get two different shapes, for example, you get both Hats and Turtles. So this is where the "special tiles" come from. $\endgroup$
    – Zeno Rogue
    Commented Mar 14 at 10:21
9
$\begingroup$

I think there's no obstruction to just greedily choosing a working color by going outwards in a spiral:

enter image description here

Each new tile never borders more than three pre-colored neighbors.

$\endgroup$
1
  • 1
    $\begingroup$ Nice suggestion. But can this be proved? $\endgroup$
    – David Roberts
    Commented Mar 25, 2023 at 6:24
6
$\begingroup$

The bijection between non-reflected tiles and a hexagonal tiling is the way to go. To construct it, we can associated to the hat tile a corresponding hexagonal tile, so that a tiling of hats gives a partial tiling of hexagons:

Hexagon associated with hat tile

This partial tiling, minus the reflected tiles, has a natural decomposition into 'triangles' constructed from hexagons, of side length 1, 2 or 3, which slide together to form a full tiling. This is probably best understood by interacting with this p5js sketch.

In a some more detail, write $T_{hex}$ for the hexagon associated to a hat tile $T$, and $T_{hex}^o$ for $T_{hex}$ minus its vertices, and call a tile face up if it is isometric to a rotation + translation of the tile above, and face down otherwise (likewise for the corresponding hexagons, which we'll colour purple and orange respectively). Then one can show that for a tiling $X$ of hats, each connected component of $\cup \{T_{hex}^o | T \in X, T\text{ face up}\}$ is constructed in one of the following three ways:

Triangles constructed from hexagons

In addition, let arrows denote the 'triangle vertices' of the 2- and 3-triangles

Arrows indicating 'vertices' of 2- and 3- triangles

Then these hexagons are adjacent or almost adjacent to reflected tiles, in the sense illustrated below.

Adjacent (left) and almost adjacent (right) hexagonal tiles

(it turns out that the vertices of the 3-triangle are always adjacent to reflected tiles, but we do not need this fact here)

The 1-triangle is either adjacent to 3 reflected tiles, or almost adjacent to 3 reflected tiles, as illustrated below.

Face down hexagons adjacent or almost adjacent to face up 1-triangle

Since any partial tiling $X_{hex}$ of hexagons coming from a tiling of hats contains a face up hexagonal tile adjacent to a face down hexagonal tile, we can assume WLOG that $X_{hex}$ contains a patch of the form:

Three face up hexagons adjacent to a face down hexagon

Proposition: such a patch is part of a larger neighbourhood:

Neighbourhood of face down hexagon surrounded by face up hexagons

Note that the 1- and 2-triangles shown above may form part of larger hex triangles.

Consider the following lines on these neighbourhoods (for convenience, we also include the patch rotated by 𝜋/3).

Curves that locally separate adjacent ribbons in one family

The red and blue curves can be extended arbitrarily far in either direction. For example, moving from left to right along the red curve in patch A, we end up traversing the top edge of a 2- or 3-triangle. The top right vertex of this triangle must be adjacent or almost adjacent to a face down hexagon, which means the top edge coincides with the top edge of the triangle on the lower left of the diagram in patch A or B, respectively, and thus the red curve can be extended further to the right.

Thus we can construct three families of curves, each of which divides the hexagons into 'ribbons' indexed by $\mathbf{Z}$. We can use these indices to define translations of all hexagons that result in the simultaneous Tetris-like move in the interactive sketch linked above.

Incidentally, the orientations of $\{T_{hex} | T \text{ face down}\}$ appear to behave similarly (at least qualitatively), so there may be a hierarchy of hat and hex tilings (possibly alternating between face up and face down dominant tiles)

$\endgroup$
1
$\begingroup$

Here are some computable colorings discovered by Simon Tatham. The algorithm is described at Appendix: four-colourings of the Hats and Spectre tilings.

Hat

Spectre

$\endgroup$
0
$\begingroup$

This tiling and colouring has translation symmetry (bold dashed line) and point symmetry (red dots and thin dashed lines). No point symmetry for the tiles under the translation axis. But it cannot tile the whole plane. It's only a frieze as one cannot continue the tiling beyond the red lines. One gets holes and/or overlap. I could not keep the same colours for the flipped tiles (bold boundary) under the translation axis as Oscar Cunningham did. Here too four tiles touching one point (can) have 4 different colours (the flipped yellow tiles can as well be cyan). Perhaps that's a sufficient rule. ColouredFriezeHAT

$\endgroup$
8
  • 1
    $\begingroup$ The question is asking about the tiling of the whole plane, given in the reference, though. $\endgroup$
    – David Roberts
    Commented Mar 27, 2023 at 20:48
  • $\begingroup$ If it bothers more than it helps, please delete it. $\endgroup$
    – P.Labarque
    Commented Mar 28, 2023 at 7:33
  • $\begingroup$ Well, it would be useful if there were some comments that indicated how this can help address the original question, otherwise it's not clear iwhat the OP can do with this answer. $\endgroup$
    – David Roberts
    Commented Mar 28, 2023 at 11:21
  • 1
    $\begingroup$ Is Appel & Haken's proof still applicable to an infinite aperiodic graph ? Such a graph with 1 region less still remains an infinite graph, right? How to apply the reduction principle then? $\endgroup$
    – P.Labarque
    Commented Mar 31, 2023 at 8:03
  • 1
    $\begingroup$ @P. that might make a good standalone question! $\endgroup$
    – David Roberts
    Commented Mar 31, 2023 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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