2 comments | Leave a comment
0xDE
14 May 2007 @ 08:35 pm
28 October 2006 @ 12:34 am
A few weeks ago I asked whether periodic tilings of the plane have periodic colorings with four colors, and if so what the relation is between the periodicity of the coloring and of the tiling. As discussed in the comments there, another way of asking the same question is, if a graph is embedded in the torus, is there a finite cover of the torus such that the lift of the graph to the cover needs only four colors?
I still don't know the answer to the question for four colors, but the answer turns out to be yes for five colors. Albertson and Stromquist [PAMS 84:449-456, 1972] showed that if a torus graph has no noncontractable cycles of length less than eight, it's five-colorable. And it's easy to find a finite cover of a torus in which any noncontractable cycle has to pass across eight copies of the original torus, hence have length at least eight. Or, put another way, for any periodic tiling of the plane, if you make the pattern of repetitions big enough so that each tile in the tiling is eight or more tiles away from its nearest repeated copy, you can use only five colors in a periodic coloring.
I still don't know the answer to the question for four colors, but the answer turns out to be yes for five colors. Albertson and Stromquist [PAMS 84:449-456, 1972] showed that if a torus graph has no noncontractable cycles of length less than eight, it's five-colorable. And it's easy to find a finite cover of a torus in which any noncontractable cycle has to pass across eight copies of the original torus, hence have length at least eight. Or, put another way, for any periodic tiling of the plane, if you make the pattern of repetitions big enough so that each tile in the tiling is eight or more tiles away from its nearest repeated copy, you can use only five colors in a periodic coloring.
11 September 2006 @ 07:33 pm
The floret pentagonal tiling is shown below with two colorings. On the left is an optimal coloring: it uses the fewest colors possible, six, among colorings that respect all translational symmetries of the tiling. The quotient of the plane tiling by these symmetries is a tiling of the torus by six tiles, in which each tile touches each other, so six colors is optimal. But on the right, we have a periodic tiling with only three colors! The trick is that it has fewer symmetries: only 1/3 of the symmetries of the uncolored tiling preserve the colors in the coloring on the right.
What can be said about this kind of problem more generally? If one has a periodic tiling of the plane, how few colors are required to color it periodically, and what can be said about the index of the coloring's symmetry group as a subgroup of the uncolored tiling's symmetries? The four-color theorem together with a standard application of König's lemma shows that any tiling has a four-coloring, but I don't see how to force the coloring to be periodic and still use only four colors in general.
ETA: Five colors suffice. Still unclear whether four colors are always possible.
What can be said about this kind of problem more generally? If one has a periodic tiling of the plane, how few colors are required to color it periodically, and what can be said about the index of the coloring's symmetry group as a subgroup of the uncolored tiling's symmetries? The four-color theorem together with a standard application of König's lemma shows that any tiling has a four-coloring, but I don't see how to force the coloring to be periodic and still use only four colors in general.
ETA: Five colors suffice. Still unclear whether four colors are always possible.