Chromatic Polynomials 13 – Knot Tricolorability

Sep 7

3 min read

Updated: Sep 7

Tricolorability is a property used to classify and distinguish different knots. Under the rules of tricolorability, a strand is a section of a knot that goes from one undercrossing to another.

The Trefoil Knot

For example, the simple trefoil knot consists of 3 strands and 3 crossings:

To “tricolor” a knot, we assign a color to each strand such that in each crossing, all three strands are the same color or all three strands are a different color. There is one more constraint – that we must use at least two colors to color the knot. We cannot color the entire knot one color and declare it to be “tricolored”.

To represent this in CPs, we will use σ₁ for Strand 1, σ₂ for Strand 2, and σ₃ for Strand 3:

For Crossing 1, we have the conditions that the three strands must all be different colors:

Or that all three strands must be the same color:

Can we just add these together to represent the OR operation?

We can, only because we know that those two conditions are mutually exclusive. To reassure ourselves that this works, we remember that applying DeMorgan’s laws to CPs gives us:

Expanding this gives us:

So, to be thoroughly rigorous, when we add our two tricolorability conditions, we should also subtract their intersection:

However, we can also see that this term will reduce to zero:

This was a bit of a diversion, but we can now be confident in adding these terms:

Since all three crossings of the trefoil know involve all three segments, we get the same terms again:

In the article “Almost a Language of Logic”, we showed that in CPs, A²=A, so we know from induction that A³=A, and that we can simplify the above condition to:

Finally, we must add a condition that we are using more than one color, or in other words, the three segments cannot all be the same color:

Using some simple reasoning we can see that the terms represented are:

(All three segments must be different colors OR All three segments are the same color) AND NOT (All three segments are the same color)

We can reduce this to:

All three segments must be different colors

Or:

Finally, the tricolorability test can be applied:

Since the number of ways to satisfy the tricolorability conditions is greater than zero, the trefoil knot is tricolorable.

A note on reducing terms: I consider reducing terms to be desirable because it reduces the processing time, but reduction isn’t required. When you get into more complicated CPs, there may be reductions that aren’t easy to see. Don’t worry about them – you will still get the right answer as long as the CP is set up correctly. I ran all the different iterations of the trefoil CP through my CP engine, and they all produced the same result.