Coloring knots (again)

A few weeks ago I mentioned the knot coloring problem, and left you to play with it. Now I’m going to say what’s going on.

First let’s remember what it means to color a knot. We take a knot and draw a knot diagram to represent it. Then we color each arc of the diagram — from the undercrossing at one end to the undercrossing at the other — either red, green, or blue. At every crossing three arcs come together, and we require that either all three get the same color or all three get different colors. We can always just give every arc the same color, but we’re interested in when we can use all three colors.

Of course you’re now screaming (or you should be) that we had to choose a diagram for the knot, so how do we know that the answer doesn’t depend on which choice we made? Luckily we have a way to tell if two knot diagrams represent the same knot: Reidemeister moves! So how do colorings behave when we do a Reidemeister move?

Let’s go through them one at a time. The first move looks like this:

Of course, it doesn’t have to be red. There’s a similar diagram for green and blue. So, if we have a strand colored red we can twist it, coloring both arcs red. On the other hand, if we have a twisted strand, both arcs have to be the same color. Otherwise the crossing wouldn’t be colored right. We can then untwist the strand.

Here’s the second move:

On the left we have two strands of different colors. After performing the move we can give the new arc the third color. If the strands were both the same color we could give the new arc that same color again. On the other side, any coloring of the right side of the move will give the same color to the top and bottom ends of each strand. We can then undo the move and still have a valid coloring.

Finally the third move:

Any coloring of the ends of the three strands that can be extended to a valid coloring of the middle on the left side can be extended to a valid coloring on the right side, and vice versa. For example, both sides require that the strand running through the middle get the same color at both ends.

Now the first and third moves don’t change the number of colors that appear. The second one seems like it might, though. If we have a coloring on the right using all three colors, maybe the left only has two? If we’re dealing with a knot (rather than a link with more than one loop) then eventually the red and green strands will have to meet up. When they do, it’s at a crossing, and then we’ll need to use blue. So if any diagram of a knot has a coloring with all three colors then all of them do. “Three-colorability” is a property of the knot itself, not just of a diagram.

Actually, we can do even better. Pick a diagram on one side of a Reidemeister move and color the ends of each strand. Either this coloring can be extended to a valid coloring of the interior of the diagram or it can’t, and if it can there’s only one way to do it. The extendible colorings of the ends of one side of a move are exactly the same as the extendible colorings of the other side.

The upshot is that we can ask about how many colorings a knot has, or even a multi-loop link. Some of them may not use all three colors, but every diagram of the same link has the same number of valid colorings. Every knot has at least three (monochromatic) colorings, so a knot is three-colorable (using all three colors) if and only if the number of valid colorings of any diagram is bigger than 3.