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.

Advertisements

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.

Continue reading Polymath16, tenth thread: Open SAT instances

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 can now 4-color the disk of radius 0.869, 5-color the disk of radius 1.1, and 6-color the disk of radius 1.85, though it appears that a larger disk is 6-colorable.

– 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.

Continue reading Polymath16, seventh thread: Upper bounds

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.

Continue reading Polymath16, sixth thread: Wrestling with infinite graphs

Polymath16, fifth thread: Human-verifiable proofs

This is the fifth “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 brief summary of the progress made in the previous thread:

– We now have a 5-chromatic unit-distance graph with 633 vertices and 3166 edges. This is the current record holder.

– We now have a human-verifiable proof that there exists a finite unit-distance graph G with a vertex v such that there is no 5-coloring of G in which v is bichromatic (see this and that). This result is “in between” \mathrm{MCNP}\geq 5 and \mathrm{CNP}\geq5, since the latter implies the result, which in turn implies the former. Domotor suggests that this might be used to prove \mathrm{CNP}\geq5.

Continue reading Polymath16, fifth thread: Human-verifiable proofs