Simon TathamFor #TilingTuesday, 4-colourings of the Penrose P2 and P3 tilings, via refinements of their substitution systems.
Penrose tilings must _admit_ proper 4-colourings, by the Four Colour Theorem and the Erdős–de Bruijn theorem. 4CT says that any finite patch of a given plane tiling must have a 4-colouring; EdB says, in that case, so does the whole plane.
But EdB doesn't provide an efficient algorithm for constructing such a colouring; it only guarantees that one exists in principle. If you wanted a large patch of 4-coloured tiling, you might have to generate a finite patch first, and then run one of the horrible algorithms from proofs of 4CT. And once you'd done it, there'd be no guarantee that _that_ 4-coloured patch would extend to a 4-colouring of the whole plane.
What you want is a refined substitution system, containing multiple types of each Penrose tile shape, each already equipped with a colour. Then you could generate tilings efficiently from that, and you'd know you had not just a finite coloured patch, but a finite patch from a whole coloured plane.
For P3 (rhombs) this is easy. Split each rhomb into a subtype for each of its 10 rotations. The adjacency graph on those 20 classes has no self-edges. There's no reason to expect that graph to be _planar_, but it turns out it can be 4-coloured anyway. So you can 4-colour a P3 tiling by assigning colours based only on tile shape and orientation.
For P2 (kites and darts), if you make the same graph, it doesn't admit a 4-colouring. But as part of my transducers research, I wrote code to refine a substitution system further, by classifying each tile based on its immediate neighbours. If I classify the P2 tiles by orientation and _then_ run a pass of that refinement algorithm, it generates 50 subtypes of kite and 40 subtypes of dart, and the adjacency graph for _those_ classes is 4-colourable. So it takes a bit more work, but it's still a substitution system that directly delivers a 4-coloured P2 tiling.
The pictures here are derived from those two refined substitution systems. In each case, the 4-colouring of the class graph was done by brute force: SageMath's first_coloring() function. So the colours aren't optimised for aesthetics!
Vuntra City
Nicole Marie T
bµg