Given the initial activity on the Polymath proposal page, Terry Tao suggested that Aubrey de Grey and I launch Polymath16 to make progress on the Hadwiger–Nelson problem. This project is a follow-up to Aubrey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.
The Hadwiger–Nelson problem is that of determining the chromatic number of the plane (CNP), defined as the minimum number of colours that must be assigned to the points of the plane in order to prevent any two points unit distance apart from being the same colour. It was first posed in 1950 and was reduced the following year to a finite graph problem; in particular, CNP is at least k if and only if there exists a finite graph of chromatic number k that can be drawn in the plane with each edge being a straight line of unit length. Such graphs are termed unit-distance graphs. It is easy to find 4-chromatic unit-distance graphs, the smallest being the 7-vertex Moser spindle.
In April 2018, Aubrey posted to the arXiv a report [deG2018] of a family of 5-chromatic unit-distance graphs. However, the smallest such graph that he discussed has 1581 vertices, and its lack of a 4-colouring requires checking for the nonexistence of particular types of 4-colourings of subgraphs of it that have almost 400 vertices, which requires a computer search.
This has led to interest in the search for simpler examples. Along these lines, our goals for this project are quite varied:
Goal 2: Reduce (ideally to zero) the reliance on computer assistance for the proof. Computer assistance was leveraged in [deG2018] to analyze a subgraph of size 397. This has so far been decreased to 278, though the corresponding full graph is actually larger than Aubrey’s original one.
Goal 3: Apply these simpler graphs to inform progress in related areas. For example:
- Find a 6-chromatic unit-distance graph.
- Improve the corresponding bound in higher dimensions.
- Improve the current record of 105/29 for the fractional chromatic number of the plane.
- Find the smallest unit-distance graph of a given minimum degree (excluding, in some natural way, boring cases like Cartesian products of a graph with a hypercube).
Following guidance from Terry Tao, we are setting a deadline for this project at Apr 15, 2019.
See this page for a newcomer’s guide to the initial approach of this project. In the short term, we are working to make further progress on Goals 1 and 2 by stitching together newly identified graphs that can substitute for the building-blocks L and M in [deG2018] and then passing them through shrinking routines of the sort described in section 5 of [deG2018].
To properly document progress on these goals, it might be helpful for participants to post links to files that contain coordinates of points in the plane and/or the resulting unit-distance graph. I launched a Dropbox folder that can serve as a repository of such files. Participants who wish to contribute a file to this folder should email me so I can grant editing privileges or post the file myself.