Color Me Polynomial

In 2015, the poet-turned-mathematician June Huh helped solve a problem posed about 50 years earlier. The problem was about complex mathematical objects called “matroids” and combinations of points and lines, or graphs. But it was also a question about polynomials — those familiar expressions from math class involving sums of variables raised to different powers.

At some point in school you were probably asked to combine, factor and simplify polynomials. For example, you may remember that x² + 2xy + y² = (x + y)². That’s a neat algebra trick, but what is it actually good for? It turns out that polynomials excel at uncovering hidden structure, a fact Huh used to great effect in his proof. Here’s a simple puzzle that illustrates how.

Suppose a game requires seating two teams of players at a square table. To prevent cheating, you avoid seating players next to someone from their own team. How many different ways can the teams be seated?

Let’s start by imagining the players as red and blue. Suppose a red player is seated at the top of our diagram, as shown here.

There are two seats adjacent to the top spot — on the right and left — so to satisfy our rule, those seats must both be taken by blue players.

The one remaining seat, at the bottom, is adjacent to two blue players, so a red player must sit there.

Since no player is sitting next to a teammate, our constraint is satisfied.

We also could have started with a blue player at the top. Similar reasoning leads to the following arrangement.

Again, no player is seated next to a player from the same team. Our constraint is satisfied, so this is another possible seating. In fact, these are the only two possible seatings. Once we choose a color for the top seat, the colors of all the other seats are completely determined.

There’s a way we can see that there are only two possible seatings without drawing all the different pictures. Let’s start at the top: We have two options, red or blue, for that seat. Once we make that choice, we have one option (the other color) for both the right and the left seats. Now, for the bottom seat, there is again only one option: the color we started with. Using the “fundamental counting principle,” we know that the total number of possibilities is the product of the number of possibilities for each choice. That gives 2 × 1 × 1 × 1 = 2 total seatings, just as we determined with our diagrams.

Now let’s add a third team with a third color. Imagine there are red, blue and yellow players. How many different seatings are possible if adjacent seats can’t be the same color? Drawing all the possibilities would take a lot of diagrams, so let’s try our counting argument instead.

There are now three colors to choose from for the top. Once that choice is made, we can choose either of the two remaining colors for the right and left spots.

What happens at the bottom of our square? It’s tempting to say there is only one option for the last seat, since it is adjacent to both the left and right seats. But do you see the problem with that reasoning?

It’s true that if the left and right are different colors, there is only one option for the bottom seat. If, for example, left is blue and right is red, then the bottom must be yellow. But what if left and right are the same color? In that case, there will be two remaining options for the bottom. This final choice is dependent upon the previous choices, and that complicates our counting.

We must consider two separate cases: when the left and right colors are the same, and when the left and right colors are different.

If the left and right colors are the same, the number of possibilities for each side looks like this:

First, we have three options for the top. Next, there are two remaining options for the right. Since we are assuming the left and right seats have the same color, we have only one option for the left: the color we used for the right. Finally, since left and right are the same color, we can choose either of the other two other colors for the bottom seat. This gives us 3 × 2 × 1 × 2 = 12 possible seatings.

Now let’s look at the possibilities when the left and right seats are different colors:

Again we have three options for the top and two options for the right. For the left, we still have only one option, but for a different reason: It can’t be the same color as the top, which is adjacent, and it can’t be the same color as the right, by assumption. And since the right and the left are two different colors, that leaves only one color for the bottom (the same color as the top). This case yields 3 × 2 × 1 × 1 = 6 possible seatings.

Since these two scenarios cover all possibilities, we just add them to get 12 + 6 = 18 total possible seatings.

Adding a third color complicated our puzzle, but our hard work will be rewarded. We can now use this strategy for 4, 5, or any q different colors.

Regardless of how many colors we have to choose from, there will always be two cases to consider: the left and right being the same color, and the left and right being different colors. Suppose we have q different colors to choose from. Here’s the diagram showing the number of options for each side when the left and right are the same color:

To begin, we have q colors to choose from for the top, and q – 1 to choose from for the right. Since we are assuming that the left and right are the same color, we have only one option for the left. That leaves q – 1 options for the bottom, which can be any color other than the one at the left and right. The fundamental counting principle gives us a total of q × (q – 1) × 1 × (q – 1) = q(q – 1)² possible seatings.

If the right and left are colored differently, we can enumerate our possibilities like this:

Again we have q options for the top and q – 1 for the right. Now, the left can’t be the same as the top or the right, so we have q – 2 options there. And the bottom can be any color that isn’t one of the two different colors used at the right or left, again leaving q – 2 options. This gives us a total of q × (q – 1) × (q – 2) × (q – 2) = q(q – 1)(q – 2)² possible seatings. Since these two situations cover all the possibilities, we add them together to find the total number of possible seatings, just as before: q(q – 1)²+ q(q – 1)(q – 2)².

This expression may seem like a strange answer to the question “How many ways can we seat different teams at a square table so that no two teammates are sitting next to each other?” But this polynomial conveys a lot of information about our problem. Not only does it tell us the numeric answers we want, it also uncovers some of the structure underlying our puzzle.

This particular polynomial is called a “chromatic polynomial,” because it answers the question: How many ways can you color the nodes of a network (or graph) so that no two adjacent nodes are the same color?

Our problem was initially about seating teams around a table, but we can easily turn it into a question about coloring the nodes of a graph. Instead of thinking about people around a table like this

we think of the people as nodes and then connect them with an edge if they are sitting next to each other.

Now, every coloring of the nodes of the graph can be thought of as a seating around the square table, where “sitting adjacent to someone” at the table is now “being connected by an edge” on the graph.

Now that we have represented our puzzle as a graph, let’s return to its chromatic polynomial. We’ll call it P(q).

P(q) = q(q – 1)² + q(q – 1)(q – 2)²

The great thing about this polynomial is that it answers our graph coloring question for all possible numbers of colors.

For example, to answer the question for three colors, we let q = 3, giving us:

P(3) = 3(3 – 1)² + 3(3 – 1)(3 – 2)² = 3 × 2² + 3 × 2 × 1² = 12 + 6 = 18

This is precisely the answer we found for the three-team puzzle above. And when we let q = 2:

P(2) = 2(2 – 1)² + 2(2 – 1)(2 – 2)² = 2 × 1² + 2 × 1 × 0² = 2 + 0 = 2

Look familiar? This is the answer to our original puzzle with only two different teams. We can find the answer for four, five or even 10 different teams, just by plugging in the appropriate value for q: P(4) = 84, P(5) = 260 and P(10) = 6,570. The chromatic polynomial has captured some fundamental structure of the problem by generalizing our counting strategy.

We can expose more structure by doing a little algebra with our polynomial P(q) = q(q – 1)² + q(q – 1)(q – 2)²:

$latex \begin{align*}
&= q(q-1)(q-1)+q(q-1)(q-2)^2\\
&= q(q-1)((q-1)+(q-2)^2)\\
&= q(q-1)(q-1+q^2-4q+4)\\
&= q(q-1)(q^2-3q+3)\\
\end{align*}$

Here we have factored q(q – 1) out of each part of our sum and then combined like terms, putting the polynomial into a “factored form,” where it is expressed as a product. And in this factored form, a polynomial can tell us about structure through its “roots.”

The roots of a polynomial are the inputs that yield zero as an output. And the factored form of a polynomial makes finding the roots easy: Since the polynomial is expressed as a product of factors, any input that makes one of the factors zero will make the whole product, and thus the polynomial, zero.

For example, our polynomial P(q) = q(q – 1)(q² – 3q + 3) has a factor of (q – 1). If we let q = 1, this factor becomes zero, which makes the entire product zero. That is, P(1) = 1(1 – 1)(1² – 3 × 1 + 3) = 1 × 0 × 1 = 0. Similarly, P(0) = 0 × (–1) × 3 = 0. So q = 1 and q = 0 are roots of our polynomial. (You might be wondering about (q² – 3q + 3). Since no real number makes this factor zero, it contributes no real roots to our chromatic polynomial.)

These algebraic roots have meaning in our graph. If we had only one color to choose from, every node would have to be the same color. It would be impossible to color the graph so that no two adjacent nodes were the same color. But this is exactly what it means for q = 1 to be a root of the chromatic polynomial. If P(1) = 0, then there are zero ways to color the graph so that adjacent nodes are not the same color. The same is true if we had zero colors to work with: P(0) = 0. The roots of the chromatic polynomial are telling us about the structure of our graph.

The power to see this structure algebraically becomes even more apparent when we start looking at other graphs. Let’s examine the triangular graph below.

How many ways are there to color this graph using q colors so that no two adjacent nodes have the same color?

As usual, there are q and q – 1 options for the first two adjacent nodes. And since the remaining node is adjacent to the first two, it must be a different color than both, leaving q – 2 options. This makes the chromatic polynomial of this triangular graph: P(q) = q(q – 1)(q – 2).

In its factored form, this chromatic polynomial tells us something interesting: q = 2 is a root. And if P(2) = 0, it must be impossible to color this graph with two colors so that no two adjacent nodes are the same. Is that really true?

Well, imagine working your way around the loop of the triangle, coloring the nodes as you go. With only two colors to choose from, you must alternate colors as you pass each node: If the first is red, then the second must be blue, which then means the third one must be red. But the first and third nodes are adjacent, so they can’t both be red. Two colors aren’t enough, just as the polynomial predicted.

Using this alternating argument, you can deduce a powerful generalization: The chromatic polynomial of any loop with an odd number of nodes must have 2 as a root. This is because if you alternate between two colors over a loop of odd length, the first and last nodes you color will always be the same. But since it’s a loop, they are adjacent. It can’t be done.

For example, we can use various techniques to determine that a loop with five nodes has the chromatic polynomial P(q) = q⁵ – 5q⁴ + 10q³ – 10q² + 4q. When we put this into factored form, it becomes P(q) = q(q – 1)(q – 2)(q² – 2q + 2). And as expected, we see that q = 2 is a root, and so P(2) = 0. Remarkably, once we establish these connections between the graphs and their polynomials, the insights cut both ways: Polynomials can tell us about the structure of graphs, and graphs can tell us about the structure of their associated polynomials.

It was a search for structure that led June Huh to prove Read’s 40-year-old conjecture about chromatic polynomials. The conjecture says that when we list the coefficients of a chromatic polynomial in order and ignore their signs, a particular condition is satisfied: Namely, the square of any coefficient must be at least the product of the two adjacent coefficients. For example, in the chromatic polynomial of our five-node loop, P(q) =q⁵ – 5q⁴ + 10q³ – 10q² + 4q, we see that 5² ≥ 1 × 10, 10² ≥ 5 × 10 and 10² ≥ 10 × 4. One thing this shows is that not every polynomial could be a chromatic polynomial: There is a deeper structure imposed on chromatic polynomials by their connections to graphs. What’s more, the connections between these polynomials and other fields led Huh and his collaborators to settle a much broader open question, Rota’s conjecture, a few years after proving Read’s conjecture.

Polynomials may be best known in their worst incarnation: as abstract exercises in the formal manipulation of algebraic expressions. But polynomials and their features — their roots, their coefficients, their various forms — help expose structure in surprising places, creating connections to the algebra all around us.

Exercises

1. A “complete” graph is a graph in which there is an edge between every pair of vertices. Find the chromatic polynomial of the complete graph on five vertices.

Click for Answer 1:
Since every vertex is adjacent to every other vertex, five different colors must be used. We can use our counting argument to find the chromatic polynomial P(q) = q(q – 1)(q – 2)(q – 3)(q – 4). What would this look like for a complete graph on n vertices?

2. Find the chromatic polynomial of the graph below. (Hint: Use what you know about chromatic polynomials of simpler graphs.)

Click for Answer 2:
This graph is a four-node loop connected to a three-node loop. We start our counting argument with q choices for the middle node. If we proceed to the left, we’ll find the chromatic polynomial of a four-node loop, which is P(q) = q(q – 1)(q² – 3q + 3). If we proceed to the right, we’ll find the chromatic polynomial of a three-node loop, which is P(q) = q(q – 1)(q – 2). Taking into consideration their common node with q choices, we can combine the results to get P(q) = q(q – 1)(q² – 3q + 3)(q – 1)(q – 2) = q(q – 1)²(q – 2)(q² – 3q + 3).

3. A graph is called “bipartite” if its vertices can be divided into two groups, A and B, so that the vertices in A are adjacent only to vertices in B, and the vertices in B are adjacent only to vertices in A. Suppose a graph G has chromatic polynomial P(q). What fact about P(q) would allow you to conclude that G is bipartite?

Click for Answer 3:
First notice that a graph is bipartite if and only if it is two-colorable. This means that, using only two colors, we can color the vertices of the graph so that no two adjacent vertices have the same color. If a graph is bipartite, we simply color the two different groups of vertices different colors. And if a graph is two-colorable, the coloring of the graph naturally determines the two groups. Thus, being bipartite is essentially the same as being two-colorable. And if a graph is two-colorable, that means there is at least one way to color the graph using two colors. So if P(q) is the chromatic polynomial of the graph, it must be the case that P(2) > 0. Similarly, the famous four-color theorem can also be stated in terms of chromatic polynomials.