AKT-09/Tricolourability

From Drorbn
Jump to: navigation, search

The tricolourability criterion for knot diagrams may be equivalently expressed as: is it possible to associate to each arc (not 'strand' since you are allowed to change color after an undercrossing; this allowance makes sense because otherwise we would end up with a single color for the whole knot; see example of how to colour a knot diagram and a picture proof that tricolourability is a isotopy invariant at http://en.wikipedia.org/wiki/Tricolorability) a member of Z/3Z such that, for each crossing, the sum of the three numbers associated to the three arcs involved is 0 mod 3 (that is, the three numbers are either all distinct or all the same) while excluding the case of associating the same number to every arc?

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 arcs) checks.)

Define the variables S_1 , ... , S_n which are associated with the arcs of a knot diagram D. Each crossing yields an equation of the form S_a + S_b + S_c = 0. We can also (without loss of generality) assume S_1 = 0. Let M be the matrix over Z/3Z encoding the aforementioned relations. The nullity of M is non-zero if and only if there is a valid tricolouring of D.