This is the sixth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’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.
Here’s a brief summary of the progress made in the previous thread:
– The smallest known unit-distance graph of chromatic number 5 now has 610 vertices and 3000 edges.
– We now have several small unit-distance graphs with no 4-coloring in which a particular vertex is bi-chromatic, and these results are human-provable.
– We now have upper bounds on the chromatic number of for .
Progress has slowed considerably since the end of the spring semester (presumably due to summer travel, etc.). I wanted to highlight a couple of questions to help keep the conversation going:
Question. Is Tamas’s result that every 4-coloring of is 8-periodic human-provable?
Terry Tao provided a comment along these lines. Actually, a human proof of can be obtained from something much weaker:
Question. Is it easy to check whether an infinite k-colorable graph has finitely many k-colorings?
Indeed, Boris has an easy proof of the following: If there exists a unit-distance graph with infinite Euclidean diameter and finitely many k-colorings, then the chromatic number of the plane is at least k+1. As such, a human proof of reduces to human-proving that has finitely many 4-colorings.
Question. What sort of lower bounds can we get on CNP if we use a version of Lovasz that’s higher on the SOS hierarchy?
We know that the (complementary) Lovasz number of the plane is about 3.48. Applying this semidefinite program to Marijn’s graph on 874 vertices gives a lower bound of about 3.37. Can we beat 3.48 by running an SOS program on one of our 5-chromatic graphs? What if we applied ideas from Oliveira’s thesis to compute with the entire plane?