The chromatic number of the plane is at least 5
The Aperiodical 2018-04-17
A long-standing mathematical problem has had a recent breakthrough – scientist Aubrey de Grey has proved that the chromatic number of the plane is at least 5.
In geometric graph theory, the Hadwiger–Nelson problem poses the question: what is the minimum number of colours required to colour the 2-dimensional plane, so that no two points that are exactly one unit of distance apart are coloured the same colour? The answer to this question is called the chromatic number of the plane.
A 7-colouring of the plane, with four-chromatic unit distance graph (image from Wikipedia)
Up until now, we knew the answer was one of 4, 5, 6 or 7. The diagram shown here contains proofs of the upper and lower bounds: for the upper bound, you can assume the hexagons are each less than one unit in diameter, and so each point inside a hexagon is one unit away from a circle of points which use only the other six colours, as the colouring has no adjacent or adjacent-but-one hexagons the same colour.
The graph in the diagram also proves the minimum is four: known as the Moser Spindle, the graph consists of two pairs of equilateral triangles, and all the arcs are one unit long. It can be used to prove a three-colouring is not possible, as follows. The colour of the top left vertex forces the other two vertices of each of the two attached triangles to use the other two colours, but this in turn forces the two lower right vertices to be the same colour, and they are a unit apart. Contradiction!
Aubrey de Grey’s graph, from the paper
Aubrey de Grey’s proof, uploaded to the arXiv earlier this month, uses a similar line of reasoning to prove it’s not possible to colour the plane with four colours in this way – only this graph has around 1600 vertices (see diagram, if you can), and the construction and checking of the graph is computer-assisted. The paper itself is still just on the arXiv for now as far as I can tell, but if we spot it being peer-reviewed and published anywhere we’ll make an update here.
In the wake of this announcement, a 16th Polymath project has been proposed to try to find a simpler graph, and improve on this result – some have conjectured it might not be possible to reduce the size of this graph further without redesigning it completely, as de Grey’s method already reduces it to as minimal as possible from the initial approach used (it involves taking smaller graphs and rotating them to align on top, much like the Moser Spindle).
Some blog posts on the topic, including one which makes attempts to verify the proof, and the paper itself, are listed below.
More information
The chromatic number of the plane is at least 5, de Grey’s paper on the ArXiv The chromatic number of the plane is at least 5, on Jordan Ellenberg’s blog Amazing progress on longstanding open problems, on Scott Aaronson’s blog The chromatic number of the plane is at least 5, on Dustin Mixon’s blog Aubrey de Grey: The chromatic number of the plane is at least 5, on Gil Kalai’s blog