Wednesday, April 18, 2018

Progress Made On 68 Year Old Math Problem

How many colours are needed to colour the plane so that no two points at distance exactly 1 from each other are the same colour? 
This quantity, termed the chromatic number of the plane or CNP, was first discussed (though not in print) by Nelson in 1950 (see [Soi]). Since that year it has been known that at least four and at most seven colours are needed. 
The lower bound was also noted by Nelson (see [Soi]) and arises because there exist 4-chromatic finite graphs that can be drawn in the plane with each edge being a straight line of unit length, the smallest of which is the 7-vertex Moser spindle [MM] (see Figure 7, left panel). 
The upper bound arises because, as first observed by Isbell also in 1950 (see [Soi]), congruent regular hexagons tiling the plane can be assigned seven colours in a pattern that separates all same-coloured pairs of tiles by more than their diameter. 
The question of the chromatic number of the plane is termed the Hadwiger-Nelson problem, because of the contributions of Nelson just mentioned and because the 7-colouring of the hexagonal tiling was first discussed (though in another context) by Hadwiger in 1945 [Had]. The rich history of this problem and related ones is wonderfully documented in [Soi]. Since 1950, no improvement has been made to either bound. 
From here.

The author, a professional scientist and amateur mathematician, proves in the linked pre-print that the lower bound is 5 and not 4.

So, the correct answer is now 5, 6 or 7, although we still don't know which of those three integers is the correct answer.

No comments: