What is the minimum number of colours needed to colour the plane in such a way that any two points that are at distance 1 from each other always have different colours? This is known as the Hadwiger–Nelson problem, and it has been an open question in geometry since 1950. This minimum number of colours is known as the chromatic number of the plane, and it follows from the picture above that the answer is either 4, 5, 6, or 7. Here’s why.
In the picture, the plane has been coloured with 7 colours (red, yellow, green, cyan, blue, magenta, and grey) and the unit distance is given by the edge length of one of the black equilateral triangles. There are no two yellow points at distance 1 from each other, because two points in the same yellow hexagon would be too close together, and two points in different yellow hexagons would be too far apart. The same observation applies to each of the other colours. This shows that it is possible to colour the plane with 7 colours so that points at distance 1 from each other always have different colours. The question is whether we can do something similar using fewer than 7 colours.
Another key ingredient in the problem is the graph above, which is called the Moser spindle. It consists of 7 points, and there is an edge between two points whenever the distance between the points is 1. The key property of the Moser spindle is that it is impossible to colour its vertices using three colours in such a way that two vertices always have different colours when they are connected by an edge. (Any attempt to do so will result in A, D, and G being the same colour, which is not allowed.) The Moser spindle can simply be drawn over any colouring of the plane, as in the top picture, and its 7 points will necessarily touch at least 4 different colours. This proves that it takes at least 4 colours to solve the Hadwiger–Nelson problem.
A similar, but much more complicated argument can be used to show that it takes at least 5 colours to satisfy the conditions of the Hadwiger–Nelson problem. The graph above, which has 1581 vertices and edges of unit length, was found by Aubrey de Grey in 2018. It can be proved (by computer, unsurprisingly) that it takes at least 5 colours to colour the vertices in such a way that two vertices at unit distance from each other always have different colours. Later, Jaan Parts found a graph with “only” 510 vertices that proves the same thing. The upshot of this is that the chromatic number of the plane must be either 5, 6, or 7.
The recent paper Extending the Continuum of Six-Colorings by Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, and Max Zimmer works towards lowering the upper bound of 7. To do this, one would need to show that there exists a colouring of the plane with 6 colours with the property that two points at distance 1 from each other always have different colours. Nobody has managed to do that yet, but the authors make some progress on a weaker version of the problem, illustrated above. Here, the plane is tiled by a repeating pattern using six colours: red, orange, yellow, green, turquoise, and blue. The larger, dotted circle has radius 1, and the smaller, dashed circle has radius d. As in the 7-colouring earlier, no two orange points lie at distance 1 from each other, and the same rules apply to the yellow, green, turquoise, and blue points. In contrast, the rule for the red points is that no two red points are allowed to be distance d apart.
Work of previous authors showed that it is possible to find colourings with these properties for d in the range 0.41 to 0.45. Ideally, we would like to be able to solve the problem for d=1, which would represent a significant breakthrough, and would prove that the chromatic number of the plane cannot be 7. Although the authors do not achieve this, they significantly expand the possible range of values of d to between 0.354 and 0.657. For the smaller values of d (between 0.354 and 0.553), the authors tile the plane with a morph of one of the building blocks shown in the picture above. As we move from left to right, the value of d increases, and the red triangle shrinks until it disappears when d is about 0.553.
The authors have a second strategy, which works if d lies between 0.418 and 0.657. This uses a different building block consisting of two pentagons, one square, four heptagons and one hexagon to tile the plane as above. The biggest circles here have radius 1, the middle ones have radius 0.657, and the small circles have radius 0.418.
The authors were able to achieve these results by formalizing colourings that were suggested by a custom machine learning algorithm. According to the paper, there is a commonly held belief that the chromatic number of the plane is 7. However, somewhat disturbingly, the answer to the question may depend on what kind of set theory is used: the approach discussed here relies on the de Bruijn–Erdős theorem, which in turn assumes the Axiom of Choice.
Picture credits and relevant links
The graphic of the 7-colouring of the plane is by David Eppstein. It appears on the Wikipedia page on the Hadwiger–Nelson problem, which is named after Hugo Hadwiger and Edward Nelson.
The graphic of the Moser spindle is by Péter Ágoston.
The picture of the graph with 1581 vertices is by Aubrey de Grey.
The other three pictures come from the paper by Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel, and Max Zimmer.
I have opened up my archive of old posts! You might be interested in the post The Illumination Conjecture, which also relates to the work of Hugo Hadwiger, and the post What is a set? which discusses the Axiom of Choice.
Substack management by Buzz & Hum.
It’s great you have opened up your archive of old posts! A very valuable resource.