This is the twelfth “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.
Activity on this project has slowed considerably, as we’ve gone 6 months without having to roll over to a new thread. As mentioned in the original thread, the deadline for this project is April 15, 2019, so we only have a couple of weeks remaining. Dömötör and Aubrey took the time to summarize the highlights of what we’ve accomplished in the last year (see below). While we don’t have a single killer result to publish, there are several branches of minor results that warrant publication. Feel free to comment on additional results that were missed in the summaries below, as well as possible venues for publication.
- Finding 5-chromatic UD graph with few vertices. The record 553-vertex graph has been published by Marijn, not much news.
- Probabilistic formulation. Here I believe we have quite interesting results, my student is planning to write his MSc thesis on it (due June).
- Bichromatic origin. Here again we have some nice small graphs (in the plane, still looking for them on the sphere), and mathematically intriguing conjectures, which would imply improved bounds for the chromatic number of the space (if we find that graph on the sphere). About an attack on a conjecture by similar copies of almost monochromatic sets with limited success (and known limitations) we will soon publish something with Nora Frankl and Tamas Hubai.
- Finding bounds for the width of the largest disk/strip that can be k-colored. We have some bounds.
- Determining the chromatic number of the extended rational field Q[w1,w2,..] for certain wi’s. I know there are some results here, but what?
Aubrey de Grey:
- Fractional CN. Jaan Parts has improved on the published record, but no one has yet computed the FCN of a 5-chromatic graph; however I put Jaan in contact with Marijn, who has much better hardware, so that may change soon. Then the question will be to find how to get a FCN above 4; presumably it will need at least a few interlocking 5-chromatic subgraphs, and that might be a clue for a 6-chromatic strategy.
- Small graphs in higher dimensions. There has been a fair bit of interest in my 59-vertex 6-chromatic graph in R^3, which is unpublished, so it should probably be described here. For completeness it may also be worth mentioning my 7-chromatic 24-vertex one in R^4, since it’s the best that has been achieved by explicit spindling and rotating and such like. My gut feeling is that the current records for higher dimensions can be beaten by spindling and rotation if only we can come up with some kind of pan-dimensional modular toolkit with which to build larger graphs, so it may be worth laying out what is so far known as a way to motivate such work.
- Upper bounds in higher dimensions. Philip coded up a nice fast way to find the most efficient colouring of a permutahedron-based tiling in higher dimensions and provided answers for R^5 and R^6; the number is still growing at about 3^n, so there seems to be a strong case for finding better tilings, especially ones in which tiles have fewer too-near neighbours. We should probably include my tiling of the plane in which each tile has onlly 16 too-near neighbours (as against 18 for the hexagonal tiling) as a way to motivate such a search in higher dimensions.
- Fraction of the plane that can be k-coloured. We have improvements (due to Jaan) for k=5 and 6, while Croft’s solution for k=4 remains unimproved (and also solves k=1, 2, 3).
- The general concept of clamping. Three families of 5-chromatic graphs (mine, Marijn’s and Dan/Geoff’s) are constructed by identifying simpler graphs with particular properties of this or that subset of vertices in any 4-colouring, and combining them so as to preclude all such properties being simultaneously true. There is sure to be masses to discover here. Way back in the first thread we had a brief exchange about finding simple M’s at the expense of more complex L’s (using graph names from my paper) but it never really went anywhere. A promising approach could be to find hexagonally symmetric graphs in which there is a hexagon (of non-unit radius) of vertices in which all three colours different from the centre are represented in any 4-colouring; I bet there are human-provable examples of that. We already have ones in which a hexagon of radius 8/3 has to all be the same colour as the centre, and there might be human-provable versions of that too.
- Measurable CNP. Marijn found a graph with 5617 vertices for which (in his words) it was “computationally hard” to find a 5 coloring with the center vertex being bichromatic. Sounds like it’s worth keeping looking for one that can’t be done, which would give MCNP >= 6.
- Siamese tilings. It turned out to be not particularly obvious how to tile the plane with seven colours in such a way that no two points of the same colour are exactly 1 apart but yet there are, irreducibly, separate tiles less than 1 apart. We never did anything much with such tilings, but they do seem to me to be so qualitatively different from ones in which all pairs of tiles are >=1 apart that we should say something about this.
- SAT-based approaches to proving the nonexistence of a 6-tiling. Boris’s original approach couldn’t find unscaleable tilings, but my suggestion for a variation seems to be theoretically more promising; however, Boris didn’t make it work. I think we should document what we did achieve so that others have a starting-point.
- On Sept 29th, Jaan optimised Philip’s brilliant 6-tiled disk from June 17th. It ended up making sense! (in terms of regular pentagons)
- Just to be sure we remember: our bounds on Euclidean dimensions of k-coloured things need to include both the largest k-tileable disks or strips and the smallest disks or strips containing a graph that is not k-colourable.