This is the second “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.
What follows is a summary of the progress made thus far:
Simplifying de Grey’s graph. There have been three strides along these lines. One is to decrease the size of the graph by iteratively removing vertices that are not necessary to be 5-chromatic. This approach has led to our current record holder, which has 826 vertices and 4273 edges. Another approach has been to hunt for more symmetric 5-chromatic graphs, in the hopes that such graphs might be easier to analyze by hand (e.g., see this and that). Finally, others have been hunting for extremely small alternatives to de Grey’s L and M graphs that are amenable to by-hand analysis, in the hopes that these would eventually lead to a 5-chromatic graph (e.g., see this and that).
Fundamental limits. In 1998, Pritikin proved that every graph with at most 12 vertices is 4-colorable, and every graph with at most 6197 vertices is 6-colorable. Pritikin’s bounds are obtained by coloring the plane with k colors and an additional “wild” color such that points of unit distance are both allowed to receive the wild color. If the wild color occupies a small fraction p of the plane, then an exercise in the probabilistic method gives that any fixed unit-distance graph with n vertices enjoys an embedding in the plane that avoids the wild color (and is therefore k-colorable) provided n<1/p. Pritikin’s coloring for the k=4 case cannot be improved without improving on the densest known subset of the plane that avoids unit distances (originally due to Croft in 1967). See this MO thread for additional information. As such, improving the bound in the k=4 case might require a new technique, whereas the k=5 and 6 cases might be amenable to optimization.
Larger k. Can we use de Grey’s graph to construct unit-distance graphs that are not 5-colorable? To answer this question, we first need to understand how 5-colorings of de Grey’s graph force small collections of vertices to be colored. Varga and Nazgand provide some thoughts along these lines. Even if we can’t stitch together a 6-chromatic unit-distance graph with these ideas, we might be able to apply them to prove that the measurable chromatic number of the plane is at least 6.
Vertices with algebraic structure. It appears as though the coordinates of our smallest 5-chromatic graph lie in (see this). If we view the plane as the complex plane, what is the smallest ring that admits a 5-chromatic single-distance graph? Every single-distance graph in the Eistenstein integers and Gaussian integers is 2-chromatic (see this). David Speyer suggests looking at next.