AKT-09/Tricolourability: Difference between revisions
m (How hard is it to compute the tricolouring invariant?) |
mNo edit summary |
||
| Line 1: | Line 1: | ||
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). |
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) while excluding the case of associating the same member to every strand. |
||
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.) |
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.) |
||
Revision as of 00:26, 16 September 2009
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) while excluding the case of associating the same member to every strand.
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.
