Category: chromatic

The chromatic number of the plane is at least …

image

A very famous open problem is the following.

How many colors are needed to color the plane so that no two points at
distance exactly 1 from each other are the same color? (This number is known as the chromatic number of the plane)

For example 2 colors are not enough. Consider 3 points that are the vertices of an equilateral triangle with side length 1. Clearly no two of these points can have the same color, so we need 3 colors just for these.  

Until this week our best knowledge was that there is a possible coloring with 7 colors, and 3 colors are not enough but we didn’t know if the best answer is 4, 5, 6 or 7.  It took more than 50 years to get something more, a couple of days ago  AUBREY D.N.J. DE GREY presented a paper on arxiv, proving that 4 colors are not enough! See here: https://arxiv.org/pdf/1804.02385.pdf

Lets see the old results.

Why is 7 color enough? Consider the following coloring:

image

Construct the hexagons such that the two opposite vertex of a hexagon are slightly closer to each other than 1. This way you cannot take two points from the same hexagon that are at distance one. If you take two points from different hexagons of the same color their distance will be at least bigger than 1. So this coloring is correct.

Why is 3 color not enough?  Consider the following 7 points. I connected the ones that are at distance 1. 

image

Can we color these points with 3 colors? Well, lets try! A,G and F must be all different, since they are connected. Also G, F and E must have three different colors. So if we color with 3 colors, A and E must have the same color. The same way we can see that A and D must have the same color. But this would mean that E and D have the same color which is not allowed! So 3 colors are not enough. 

Booth of these were very easy to see, but until now we couldn’t do better. 

So what is new?

AUBREY D.N.J. DE GREY proved that 4 colors are not enough. The proof is similar to the one above, but much more complicated. Some parts even used computer verification. On the following picture there are 1567 yellow points, and every pair is connected if their distance is 1. It is a lot of points, so it is not really visible :\

image

He showed that 4 color is not enough for these points, we need at least 5. This result doesn’t settle the problem, we still don’t know if 5 colors are enough for the whole plane, but we are closer to the answer. 

There is a lot of interesting things connected to this problem maybe I will make some posts about it later.