AKT-09/Tricolourability: Difference between revisions
No edit summary |
m (How hard is it to compute the tricolouring invariant?) |
||
| Line 3: | Line 3: | ||
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.) |
||
Define the variables S1...Sn which are associated with the strands of a knot diagram D. Each crossing yields an equation of the |
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. |
||
Revision as of 01:25, 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).
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.
