AKT-09/Tricolourability - Revision history

Lzhang: corrected terminology 'strand' -> 'arc'

2009-09-18T23:13:40Z

corrected terminology 'strand' -> 'arc'

← Older revision		Revision as of 19:13, 18 September 2009
Line 1:		Line 1:
	{{AKT-09/Navigation}}		{{AKT-09/Navigation}}
	The tricolourability criterion for knot diagrams may be equivalently expressed as: is it possible to associate to each ~~strand~~ (~~I am~~ not ~~sure what is the correct terminology, but~~ '~~segment~~' ~~is a more intuitive term for me as~~ 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 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 ~~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~~?		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 ~~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 arcs) 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.		Define the variables <math>S_1 , ... , S_n</math> which are associated with the arcs 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.

Lzhang: clearified my confusion with the usage of the word 'strand'; added link to demonstration of knot coloring

2009-09-18T21:21:08Z

clearified my confusion with the usage of the word 'strand'; added link to demonstration of knot coloring

← Older revision		Revision as of 17:21, 18 September 2009
Line 1:		Line 1:
	{{AKT-09/Navigation}}		{{AKT-09/Navigation}}
	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?		The tricolourability criterion for knot diagrams may be equivalently expressed as: is it possible to associate to each strand (I am not sure what is the correct terminology, but 'segment' is a more intuitive term for me as 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 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 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.)		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.		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.

Drorbn at 01:01, 17 September 2009

2009-09-17T01:01:05Z

← Older revision		Revision as of 21:01, 16 September 2009
Line 1:		Line 1:
			{{AKT-09/Navigation}}
	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?		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?

Nadish at 06:25, 16 September 2009

2009-09-16T06:25:19Z

← Older revision		Revision as of 02:25, 16 September 2009
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) while excluding the case of associating the same ~~member~~ to every strand.		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.)		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.		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.

Nadish at 06:17, 16 September 2009

2009-09-16T06:17:08Z

← Older revision		Revision as of 02:17, 16 September 2009
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 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.		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.

Nadish at 05:26, 16 September 2009

2009-09-16T05:26:54Z

← Older revision		Revision as of 01:26, 16 September 2009
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.)

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

2009-09-16T05:25:33Z

How hard is it to compute the tricolouring invariant?

← Older revision		Revision as of 01:25, 16 September 2009
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 ~~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.		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.

Nadish at 05:14, 16 September 2009

2009-09-16T05:14:30Z

New page

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.