The chromatic number of the plane, part 4: an upper bound

In my previous posts I explained lower bounds for the Hadwiger-Nelson problem: we know that the chromatic number of the plane is at least 5 because there exist unit distance graphs which we know need at least 5 colors. Someday, perhaps someone will succeed in constructing an even bigger unit distance graph that requires 6 colors, and then we’ll know CNP \geq 6.

But what about an upper bound? Can we say for sure that the CNP has to be smaller than some limit? Indeed, we can: we know that CNP \leq 7. Today I want to explain how we can show that CNP \leq 9; in another post I’ll show the proof that CNP \leq 7.

Proving an upper bound for the chromatic number of the plane is very different than proving a lower bound. A lower bound is all about showing that you can’t color the plane with a certain number of colors. An upper bound, on the other hand, is all about showing that you can. We know that CNP \leq 7 because there is a specific, valid way to color the plane using only seven colors! It might be possible to do it with fewer colors, using a very clever pattern, which is why 7 is only an upper bound. But at least we know it can be done with 7.

Let’s start with something simpler. Imagine coloring the whole plane with a repeating pattern like this:

Can this be a valid coloring of the plane? (Of course, we already know it can’t because it only uses four colors, and CNP > 4; but let’s see if we can give a more direct argument why this is not valid). First of all, the squares can’t be too big: we don’t want any pair of points inside the same square to be 1 unit apart. This means the diagonal of each square has to be less than 1.

So if the diagonals of the squares are less than 1, the sides of the squares have to be less than 1 / \sqrt 2. But the problem is that squares of the same color also have to be far enough apart so that no two points in same-colored squares are 1 unit apart. But in this scenario same-colored squares are separated by only one other square; if the sides of the squares is < 1 / \sqrt 2 \approx 0.707 then they are too close.

This idea can be easily salvaged, however: we just need more colors!

Now we are using nine colors, with a 3 \times 3 repeating pattern instead of 2 \times 2. Let’s see if we can make this work. Once again, the squares can’t be too big (lest two points inside the same square can be 1 unit apart) but same-color squares can’t be too close (lest two points in different same-color squares can be 1 unit apart). Call s the side length of the squares. The first condition once again gives us s < 1/\sqrt 2. What about the second condition? The shortest distance between two same-colored squares is now 2s, if you travel straight east-west or north-south. (You can confirm for yourself that any other line between same-colored squares is longer.) So we must have 2s > 1.

Can we pick a value of s that makes s < 1/\sqrt 2 and 2s > 1 both true? Yes! Rearranging a bit, this just says 1/2 < s < 1/\sqrt 2. Since 1/2 < 1/\sqrt 2 this gives us a valid range of values for s; any such value for s gives us a valid 9-coloring of the plane.

Hence, it is possible to color the plane using 9 colors, such that no two points at distance 1 from each other have the same color! We don’t know if this is the best way to color the plane (in fact, it isn’t!), but at least we know it is a way. So this shows that CNP \leq 9.

In my next post I’ll explain how we know that CNP \leq 7: the proof is similar in spirit, but more complex (and, of course, more efficient) due to its use of hexagons instead of squares.

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in geometry, proof and tagged , , , , , , . Bookmark the permalink.

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.