Algorithm for tricoloring a knot

Question

I have just started studying knot theory, and read about tricolorability of knots. Two knots are equivalent iff they are tricolorable. While trying to color a variety of complex knots, I tried a backtracking approach of starting with an arbitrary arc to color, coloring upto a point where there is no possibility of doing a valid coloring and then backtracking to the last point where I made a choice of color to continue with a different choice of color from there. I wished to know if there is a standard algorithm for coloring knots.

Answer 1

For Fox $n$-colorings in general, one colors the arcs with elements from $\{0,1,\dots,n-1\}$ constrained to a certain linear equation at each crossing. For $3$-colorings, the equation is

The reduction is using the fact that $1\equiv -2\pmod{3}$. One can check that $a+b+c\equiv 0\pmod{3}$ means that either all three variables have the same value or all have different values.

For example, here is a figure-eight knot along with the associated linear system and its matrix:

I asked Mathematica to compute the nullspace of this matrix modulo $3$ with

NullSpace[{{1, 0, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {0, 1, 1, 1}}, Modulus -> 3]

and it gave back {{1,1,1,1}}, signifying that the only tricolorings are trivial. Therefore the figure-eight knot is not nontrivially tricolorable.

On the other hand, here is the trefoil knot:

According to Mathematica,

In[108]:= NullSpace[{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}, Modulus -> 3]

Out[108]= {{2, 0, 1}, {2, 1, 0}}

Thus the space of tricolorings is two-dimesional. One nontrivial one is given by $a=2$, $b=0$, and $c=1$.

(To calculate the nullspace yourself, you do Gaussian elimination modulo $3$. Then you can read off a basis for the nullspace like you would usually do in linear algebra. It's just all done modulo $3$.)

---

Something I didn't mention with the above systems is that, because it turns out tricolorings are linear, you can subtract off the trivial component, letting you assume one of the variables is $0$. You can cross off any column of the matrix to effect this assumption. Secondly, there is a linear dependence on the rows, so you can cross off any row. Hence, given an $n$-crossing knot, you can create an $(n-1)\times(n-1)$ matrix through this process. The nonzero elements in the nullspace of this matrix is exactly the collection of nontrivial tricolorings. (In one of my comments on the question, this is the matrix whose determinant is divisible by $3$ iff the knot is tricolorable.)