This is the thirteenth “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.

Interest in this project has spiked since approaching (and passing) our original deadline of April 15. For this reason, I propose we extend the deadline to October 15, 2019. We can discuss this in the Polymath proposal page.

Here are some recent developments:

I’m interested to see if this last point has legs!

## Polymath16, eleventh thread: Chromatic numbers of planar sets

This is the eleventh “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:

– Let w(k) denote the supremum of w such that $[0,w]\times\mathbb{R}$ is k-colorable. Then of course $w(1)=-\infty$ and $w(k)=\infty$ for every $k\geq 7$. Furthermore,

$\displaystyle{w(2)=0, \quad w(3)=\frac{\sqrt{3}}{2}, \quad w(4)\geq\sqrt{\frac{32}{35}}, \quad w(5)\geq\frac{13}{8}, \quad w(6)\geq \sqrt{3}+\frac{\sqrt{15}}{2}.}$

Colorings that produce these lower bounds are depicted here. The upper bound for k=3 is given here.

– The largest known k-colorable disks for k=2,3,4,5 are depicted here.

Presumably, we can obtain descent upper bounds on w(4) by restricting (a finite subset of) the ring $\mathbb{Z}[\omega_1,\omega_3,\omega_4]$ to an infinite strip.

## Polymath16, tenth thread: Open SAT instances

This is the tenth “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:

– We have new results in the probabilistic formulation, namely, Proposition 36 and Lemmas 38 and 39.

Jaan Parts refined Pritikin’s analysis to prove that every unit-distance graph with at most 24 vertices is 5-colorable, and every such graph with at most 6906 vertices is 6-colorable.

Domotor, Frankl and Hubai showed that, if there exists a k-chromatic unit-distance graph with a bichromatic origin such that all its neighbors are in the upper half-plane and all their coordinates are rational, then CNP is at least k.

## Polymath16, ninth thread: Searching for a 6-coloring

This is the ninth “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:

We can now 6-color $[0,2]\times\mathbb{R}$.

– We now have a laundry list of necessary conditions for a certain family of tile-based 6-colorings of the plane.

The next step is to search for a 6-coloring of the plane. The basic idea is to build up colored plane graphs and prune with our necessary conditions. We were hoping that existing code to generate plane graphs (namely, plantri) could be used as a blackbox for this search, but after further inspection, it seems that we’ll have to write this code ourselves. (When building up plane graphs, we will be adding vertices to the outer face, whereas plantri treats all faces equally.)

## Polymath16, eighth thread: More upper bounds

This is the eighth “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:

– We now have a human proof that $p_d<0.49$ for $d \geq 0.52$.

There is ongoing work to improve Thomassen’s result so that the tiles need not be strictly smaller than 1 nor have distance strictly larger than 1. This would produce new obstructions to 6-coloring the plane.

## Polymath16, seventh thread: Upper bounds

This is the seventh “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 now has 553 vertices and 2722 edges.

– Terry Tao made some progress on understanding the colorings of $R_2$.

## Polymath16, sixth thread: Wrestling with infinite graphs

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 $\mathbb{R}^d$ for $d=5,6$.