This is the third “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.
Currently, our smallest 5-chromatic unit-distance graph has 803 vertices and 4144 edges. Much of the other progress has been in finding new 4- and 5-chromatic graphs, and hunting for features that make the chromatic number so large. I wanted to outline the role that algebraic structure appears to play in our progress to date:
Denote . Many of our constructions can be viewed as finite subsets of rings:
- , known as the Eisenstein integers and the hexagonal lattice, is 3-chromatic.
- contains 4-chromatic graphs such as the Moser spindle, Golomb’s graph (see this), and de Grey’s M. The entire ring appears to be 4-colorable by homomorphic coloring.
- contains de Grey’s original 5-chromatic graph N.
- contains 5-chromatic graphs due to Marijn and Tamás.
- contains a 5-chromatic graph due to Jannis.
Let denote the set of complex numbers of unit modulus. Instead of , several comments in the previous thread consider another ring generated by , where and . The inclusion of is helpful since it appears in :
Furthermore, by including the inverses of and in , these members are distinguished as units in the ring, making them easier to work with algebraically. In general, we want to keep track of which members of our ring have unit modulus, since these generate the edges in our Cayley graph.
Question. Given a subring of , how do we identify the members of ?
Question. Is it the case that ?
By design, any ring containing and a complex number of squared modulus will also contain . Tamás identified yet another member of , and the corresponding edges are critical to the Cayley graph being 5-chromatic.
Once has been determined, one may hunt for homomorphic colorings of .
Question. Does admit a homomorphic 5-coloring?
Question. Does there exist such that does not admit a homomorphic 5-coloring?
In theory, we could use the absence of homomorphic colorings to flag the possible nonexistence of a coloring, and then run a SAT solver on a 3-fold (say) Minkowski sum of an appropriate finite subset of to establish nonexistence. (Warning: This may lead to many false positives considering the entire plane is not homomorphically colorable.)