Difference between revisions of "HadwigerNelson problem"
From Polymath Wiki
(Created page with "The Chromatic Number of the Plane (CNP) is the chromatic number of the graph whose vertices are elements of the plane, and two points are connected by an edge if they are a un...") 
(No difference)

Revision as of 20:21, 13 April 2018
The Chromatic Number of the Plane (CNP) is the chromatic number of the graph whose vertices are elements of the plane, and two points are connected by an edge if they are a unit distance apart. The HadwigerNelson problem asks to compute CNP. The bounds [math]4 \leq CNP \leq 7[/math] are classical; recently [deG2018] it was shown that [math]CNP \geq 5[/math].
Blog posts and other online forums
 Has there been a computer search for a 5chromatic unit distance graph?, Juno, Apr 16, 2016.
 The chromatic number of the plane is at least 5, Jordan Ellenberg, Apr 9 2018.
 Aubrey de Grey: The chromatic number of the plane is at least 5, Gil Kalai, Apr 10 2018.
 Polymath proposal: finding simpler unit distance graphs of chromatic number 5, Aubrey de Grey, Apr 10 2018.
 The chromatic number of the plane is at least 5, Dustin Mixon, Apr 10, 2018.
 Amazing progress on longstanding problems, Scott Aaronson, Apr 11 2018.
 https://dustingmixon.wordpress.com/2018/04/13/thechromaticnumberoftheplaneisatleast5partii/, Dustin Mixon, Apr 13 2018.
Code and data
 The 1585vertex graph in DIMACS format
 A naive translation of 4colorability of this graph into a SAT problem in DIMACS format
 The vertices of this graph in explicit Sage notation
Wikipedia
Bibliography
 [deG2018] [The chromatic number of the plane is at least 5, Aubrey D.N.J. de Grey, Apr 8 2018.
 [P1998] D. Pritikin, All unitdistance graphs of order 6197 are 6colorable, Journal of Combinatorial Theory, Series B 73.2 (1998): 159163.