AKT-09/Tricolourability

The tricolourability criterion for knot diagrams may be equivalently expressed as: is it possible to associate to each strand a member of Z/3Z such that, for each crossing, the sum of the three numbers associated to the three strands involved is 0 mod 3 (that is, the three numbers are either all distinct or all the same).

This fact can be exploited to give an algorithm for determining tricolourability of a knot diagram whose complexity is polynomial in the number of crossings. (A naive test which tried all possible colourings would require 3^(number of strands) checks.)

Define the variables S1...Sn which are associated with the strands of a knot diagram D. Each crossing yields an equation of the form Sa + Sb + Sc = 0. We add the restriction S1 = 0 (without loss of generality) and with the added benefit that the trivial colouring is easily recognized as the trivial solution to the equation Mx = 0 where x = (S1, ..., Sn) and M is the matrix over Z/3Z encoding the aforementioned relations. The rank of M is non-zero if and only if there is a valid tricolouring of D.