Drorbn - User contributions [en]

AKT-09/Tricolourability

2009-09-16T06:25:19Z

Nadish:

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 number 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 <math>S_1 , ... , S_n</math> which are associated with the strands of a knot diagram D. Each crossing yields an equation of the form <math>S_a + S_b + S_c = 0</math>. We can also (without loss of generality) assume <math>S_1 = 0</math>. 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.

AKT-09/Tricolourability

2009-09-16T06:17:08Z

Nadish:

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 nullity of M is non-zero if and only if there is a valid tricolouring of D.

AKT-09/Tricolourability

2009-09-16T05:26:54Z

Nadish:

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.

AKT-09/Tricolourability

2009-09-16T05:25:33Z

Nadish: How hard is it to compute the tricolouring invariant?

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.

Notes for AKT-090910-2/0:51:07

2009-09-16T05:18:16Z

Nadish:

Dror suggests two problems to think about:

: 1. How hard is it to compute I, the colouring invariant. (See [[AKT-09/Tricolourability]] for a proposed simple procedure.)<BR>
: 2. How powerful is the Jones polynomial? (See the next class for the answer.)

Notes for AKT-090910-2/0:51:07

2009-09-16T05:16:05Z

Nadish:

Dror suggests two problems to think about:

1. How hard is it to compute I, the colouring invariant. (See [[AKT-09/Tricolourability]] for a proposed simple procedure.)
2. How powerful is the Jones polynomial? (See the next class for the answer.)

AKT-09/Tricolourability

2009-09-16T05:14:30Z

Nadish:

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 first 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.