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 .

Advertisements

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

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 with a vertex such that there is no 5-coloring of in which is bichromatic (see this and that). This result is “in between” and , since the latter implies the result, which in turn implies the former. Domotor suggests that this might be used to prove .

Polymath16, fourth thread: Applying the probabilistic method

This is the fourth “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 some of the main directions of this project:

— Lower bounds from the probabilistic method —

Terry Tao suggested a new approach that might lead to a human proof of :

Suppose there exists a 4-coloring , and apply a “uniform random” Euclidean isometry to and permutation to to produce a random 4-coloring (this can be made rigorous since is amenable). Then for each , we can estimate probabilities of the form by considering all proper 4-colorings of . Different can then produce inconsistent probability estimates, resulting in the desired contradiction.

Polymath16, third thread: Is 6-chromatic within reach?

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:

Polymath16, second thread: What does it take to be 5-chromatic?

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

Polymath16, first thread: Simplifying de Grey’s graph

Given the initial activity on the Polymath proposal page, Terry Tao suggested that Aubrey de Grey and I launch Polymath16 to make progress on the Hadwiger–Nelson problem. This project is a follow-up to Aubrey’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.

The Hadwiger–Nelson problem is that of determining the chromatic number of the plane (CNP), defined as the minimum number of colours that must be assigned to the points of the plane in order to prevent any two points unit distance apart from being the same colour. It was first posed in 1950 and was reduced the following year to a finite graph problem; in particular, CNP is at least k if and only if there exists a finite graph of chromatic number k that can be drawn in the plane with each edge being a straight line of unit length. Such graphs are termed unit-distance graphs. It is easy to find 4-chromatic unit-distance graphs, the smallest being the 7-vertex Moser spindle.