About a week ago, Aubrey de Grey published a paper titled “The chromatic number of the plane is at least 5”, which is a really cool result. It’s been widely reported already, so I’m actually a bit late to the party. But in my usual way, I’d like to take a more leisurely approach to explaining the math in more detail. In this post, I’ll explain what the problem is; in upcoming posts I’ll explain what we know about the problem, and how de Grey’s paper fits in.

Graph colorings and chromatic numbers

Suppose we have a graph with vertices connected by (bidirectional) edges. One natural task is to assign a color to each vertex of in such a way that for every edge, the two vertices at the ends of the edge have different colors. Put another way, no two vertices connected by an edge should have the same color. This is called a (vertex) coloring of .

For example, here is a graph with a valid coloring (using four colors):

If you look at any edge in this graph, you can see that the two vertices at the ends of the edge have different colors.

As an example of why we might care about this, suppose we have a graph where the vertices represent people, and two people are connected by an edge if they are enemies. Then a vertex coloring corresponds to a way to assign everyone to a team (one team for each color) such that enemies are never on the same team! Here’s another example: suppose vertices represent courses, and there is an edge between two courses if there is at least one student who is signed up for both courses. Then a vertex coloring is a way to schedule courses—each “color” represents a different time slot—such that no student has a conflict. Or if vertices represent countries, and there is an edge between two vertices whenever those countries share a border, a coloring of the graph is a way to literally color a map so bordering countries never have the same color. (Famously, for any (non-weird) map you can do this using only four colors; this is something I’d like to write more about someday.) These examples are just the tip of the iceberg: this is a natural problem that comes up all the time in practice.

Given a graph , coming up with a vertex coloring is trivial: just make every vertex a different color! But this is silly; typically, it is better to use fewer colors, so although giving every vertex a different color results in a valid vertex coloring, it is not a very good one. The natural question to ask is: given a graph , what is the smallest possible number of colors needed to construct a vertex coloring? This smallest possible number is called the chromatic number of (and is often written ).

For example, consider the following three graphs:

The graph on the left has chromatic number 2: we can’t use only one color since then the edges would have vertices of the same color on both ends, but we can get away with only two colors since there’s nothing to prevent the vertices on the ends from having the same color as each other, as long as they have a different color than the middle vertex. On the other hand, the graph in the middle has chromatic number 3: since each vertex is adjacent to both other vertices, we actually need to give every vertex its own distinct color.

The graph on the right is the same as the example graph I showed before, with a coloring using four vertices. So is the chromatic number four? Not so fast! At this point we only know the chromatic number is at most four. I will leave you the following exercises:

1. Explain why it is not possible to color the vertices of this graph using only two colors.
2. Either show a way to color the vertices using only three colors, or explain why it is not possible.

The chromatic number of the plane

It’s a bit of a stretch, but we can generalize this to ask about the “chromatic number” not of a graph, but of the plane. In particular, we want to assign a color to every point on the plane such that any two points which are exactly 1 unit apart have different colors. Notice that the plane contains infinitely many points (uncountably many, in fact), so we certainly can’t hope to color them by simply listing all the points and giving a color to each! In essence, we are looking for a function such that for any points and , if the distance between and (computed using the distance formula, aka Pythagorean Theorem) is exactly 1, then .

You can think of a function as an (infinite) “picture” or “painting”. Imagine looking at a painting and holding up a 1-inch ruler next to it. No matter where you place the ruler and no matter which way you turn it, the two points at opposite ends of the ruler always have different colors! What could such a painting look like? And how many colors does it need?

The minimum number of colors needed is known as the chromatic number of the plane, abbreviated CNP. The problem of determining CNP (known as the Hadwiger-Nelson problem) was first posed around 1950, and we have known for a long time that the answer is somewhere between and , inclusive. (I will explain how we know this in later posts!) De Grey’s contribution was to show that the answer can’t be ; hence we now know that the answer has to be , , or —but we still don’t know which!