User:Leo algknt - Revision history

Leo algknt at 00:47, 25 May 2018

2018-05-25T00:47:59Z

← Older revision		Revision as of 20:47, 24 May 2018
Line 31:		Line 31:

	'''Attempt 2''': The time complexity for looping through <math>n</math> crossing is <math>\bigcirc(n)</math>. Now at each of the <math>n</math> crossing, three arcs meet and deciding which of the three colours to colour them is also of complexity <math>\bigcirc(n^3)</math>.		'''Attempt 2''': The time complexity for looping through <math>n</math> crossing is <math>\bigcirc(n)</math>. Now at each of the <math>n</math> crossing, three arcs meet and deciding which of the three colours to colour them is also of complexity <math>\bigcirc(n^3)</math>.




			'''Question 2'''
			Consider a crossing <math>X1</math> where component 1 is above component 2. If we trace component 1 from <math>X1</math> to another crossing <math>X2</math> with component 1 now below component 2, the <math>X1</math> and <math>X2</math> have the same sign.

			Now in the definition of linking number of two component link, we add up all the signs of the crossings between the two components and divide by 2 since we count these sings twice. If we count only the crossing where component 1 is above component two, then we need not divide by 2. This proves the first equality. The second equality is similar in argument. We just need to switch crossings.

Leo algknt at 05:53, 24 May 2018

2018-05-24T05:53:43Z

← Older revision		Revision as of 01:53, 24 May 2018
Line 30:		Line 30:


	'''Attempt 2''': The time complexity for looping through <math>n</math> crossing is <math>\~~Big~~(n)</math>. Now at each of the <math>n</math> crossing, three arcs meet and deciding which of the three colours to colour them is also of complexity <math>\~~Big~~(n^3)</math>.		'''Attempt 2''': The time complexity for looping through <math>n</math> crossing is <math>\bigcirc(n)</math>. Now at each of the <math>n</math> crossing, three arcs meet and deciding which of the three colours to colour them is also of complexity <math>\bigcirc(n^3)</math>.

Leo algknt at 05:53, 24 May 2018

2018-05-24T05:53:05Z

← Older revision		Revision as of 01:53, 24 May 2018
Line 27:		Line 27:

	''		''
	From '''Part A''', we can compute the rank of the <math>M</math> (M is a result of <math>n</math> linear equations coming from <math>n</math> crossings of a knot diagram) using Gaussian elimination and this can be done in polynomial time. From the rank nullity theorm, we get the nullity and hence <math>\lambda(K)</math>.		'''Atempt 1''': From '''Part A''', we can compute the rank of the <math>M</math> (M is a result of <math>n</math> linear equations coming from <math>n</math> crossings of a knot diagram) using Gaussian elimination and this can be done in polynomial time. From the rank nullity theorm, we get the nullity and hence <math>\lambda(K)</math>.


			'''Attempt 2''': The time complexity for looping through <math>n</math> crossing is <math>\Big(n)</math>. Now at each of the <math>n</math> crossing, three arcs meet and deciding which of the three colours to colour them is also of complexity <math>\Big(n^3)</math>.

Leo algknt at 05:38, 24 May 2018

2018-05-24T05:38:22Z

← Older revision		Revision as of 01:38, 24 May 2018
Line 20:		Line 20:
	so that <math>a\wedge b + a + b \equiv 0\mod 3</math>.		so that <math>a\wedge b + a + b \equiv 0\mod 3</math>.

	Then, with the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3} \equiv 0\mod 3</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in {1, 2, \ldots, n}</math>. Thus we get a system of <math>n</math> linear equation, from which we get a matrix <math>M</math>. The nullspace <math>\mathrm{Null}(M)</math> of <math>M</math> is the solution to this system of equation and this is exactly the set of all 3-colourings of <math>D</math>. This is a vector space of size <math>\lambda(K) =\|\mathrm{Null}(M)\| = 3^{\dim(\mathrm{Null}(M))}</math>		Then, with the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3} \equiv 0\mod 3</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in \{1, 2, \ldots, n\}</math>. Thus we get a system of <math>n</math> linear equation, from which we get a matrix <math>M</math>. The nullspace <math>\mathrm{Null}(M)</math> of <math>M</math> is the solution to this system of equation and this is exactly the set of all 3-colourings of <math>D</math>. This is a vector space of size <math>\lambda(K) =\|\mathrm{Null}(M)\| = 3^{\dim(\mathrm{Null}(M))}</math>

Leo algknt at 05:36, 24 May 2018

2018-05-24T05:36:01Z

← Older revision		Revision as of 01:36, 24 May 2018
Line 3:		Line 3:
	'''Question 1.'''		'''Question 1.'''

	A. ''Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3		A. ''Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3.


	''		''
	'''Attempt''': Let <math>D</math> be a knot diagram for the knot <math>K</math> with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by		'''Attempt''': Let <math>D</math> be a knot diagram for the knot <math>K</math> with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by

Leo algknt at 05:25, 24 May 2018

2018-05-24T05:25:16Z

← Older revision		Revision as of 01:25, 24 May 2018
Line 25:		Line 25:

	''		''
	From ~~part~~ A, we can compute the rank of the <math>M</math> (M is a result of <math>n</math> linear equations coming from <math>n</math> crossings of a knot diagram) using Gaussian elimination and this can be done in polynomial time. From the rank nullity theorm, we get the nullity and hence <math>\lambda(K)</math>.		From '''Part A''', we can compute the rank of the <math>M</math> (M is a result of <math>n</math> linear equations coming from <math>n</math> crossings of a knot diagram) using Gaussian elimination and this can be done in polynomial time. From the rank nullity theorm, we get the nullity and hence <math>\lambda(K)</math>.

Leo algknt at 05:24, 24 May 2018

2018-05-24T05:24:41Z

← Older revision		Revision as of 01:24, 24 May 2018
Line 3:		Line 3:
	'''Question 1.'''		'''Question 1.'''

	A. Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3		A. ''Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3
			''

	Attempt: Let <math>D</math> be a knot diagram for the knot <math>K</math> with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by		'''Attempt''': Let <math>D</math> be a knot diagram for the knot <math>K</math> with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by


Line 15:		Line 15:
	c, & a\not= b		c, & a\not= b
	\end{array}		\end{array}
	\right.</math>		\right.</math>,
	so that <math>a\wedge b + a + b \equiv 0\mod 3</math>.		so that <math>a\wedge b + a + b \equiv 0\mod 3</math>.

	Then, with the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3} \equiv 0\mod 3</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in {1, 2, \ldots, n}</math>. Thus we get a system of <math>n</math> linear equation, from which we get a matrix <math>M</math>. The nullspace <math>\mathrm{Null}(M)</math> of <math>M</math> is the solution to this system of equation and this is exactly the set of all 3-colourings of <math>D</math>. This is a vector space of size <math>\lambda(K) = 3^{\|\mathrm{Null}(M)\|}</math>		Then, with the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3} \equiv 0\mod 3</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in {1, 2, \ldots, n}</math>. Thus we get a system of <math>n</math> linear equation, from which we get a matrix <math>M</math>. The nullspace <math>\mathrm{Null}(M)</math> of <math>M</math> is the solution to this system of equation and this is exactly the set of all 3-colourings of <math>D</math>. This is a vector space of size <math>\lambda(K) =\|\mathrm{Null}(M)\| = 3^{\dim(\mathrm{Null}(M))}</math>



		⚫	''B. Prove that <math>\lambda(K)</math> is computable in polynomial time in the number of crossings of K.
	Let

			''
⚫	B. Prove that <math>\lambda(K)</math> is computable in polynomial time in the number of crossings of K.
			From part A, we can compute the rank of the <math>M</math> (M is a result of <math>n</math> linear equations coming from <math>n</math> crossings of a knot diagram) using Gaussian elimination and this can be done in polynomial time. From the rank nullity theorm, we get the nullity and hence <math>\lambda(K)</math>.

Leo algknt at 04:49, 24 May 2018

2018-05-24T04:49:47Z

← Older revision		Revision as of 00:49, 24 May 2018
Line 5:		Line 5:
	A. Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3		A. Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3

	Attempt: Let <math>D</math> be a knot diagram with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by		Attempt: Let <math>D</math> be a knot diagram for the knot <math>K</math> with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by


Line 16:		Line 16:
	\end{array}		\end{array}
	\right.</math>		\right.</math>
	so that <math>a\wedge b + a + b \~~cong~~ 0\mod 3</math>		so that <math>a\wedge b + a + b \equiv 0\mod 3</math>.

	~~With~~ the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3}</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in {1, 2, \ldots, n}</math>. Thus we get a system of <math>n</math> linear equation.		Then, with the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3} \equiv 0\mod 3</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in {1, 2, \ldots, n}</math>. Thus we get a system of <math>n</math> linear equation, from which we get a matrix <math>M</math>. The nullspace <math>\mathrm{Null}(M)</math> of <math>M</math> is the solution to this system of equation and this is exactly the set of all 3-colourings of <math>D</math>. This is a vector space of size <math>\lambda(K) = 3^{\|\mathrm{Null}(M)\|}</math>

Leo algknt at 04:29, 24 May 2018

2018-05-24T04:29:06Z

← Older revision		Revision as of 00:29, 24 May 2018
Line 3:		Line 3:
	'''Question 1.'''		'''Question 1.'''

	A. Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb F}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3		A. Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb Z}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3

	Attempt: Let <math>D</math> be a knot diagram with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in ~~\mathbb~~{~~Z}/3~~\mathbb{Z}</math> represent the arcs. Now let <math>a,b,c \in \mathbb{Z}/3\mathbb{Z}</math> ~~, with~~		Attempt: Let <math>D</math> be a knot diagram with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in {\mathbb Z}_3</math> represent the arcs. Now let <math>a,b,c \in {\mathbb Z}_3</math>. Define <math>\wedge : {\mathbb Z}_3 \times {\mathbb Z}_3 \rightarrow {\mathbb Z}_3</math> by


Line 16:		Line 16:
	\end{array}		\end{array}
	\right.</math>		\right.</math>
			so that <math>a\wedge b + a + b \cong 0\mod 3</math>

			With the above definition, we get a linear equation <math>a_{i_1} + a_{i_2} + a_{i_3}</math> for each each of the <math>n</math> crossings, where <math>i_1, i_2, i_3 \in {1, 2, \ldots, n}</math>. Thus we get a system of <math>n</math> linear equation.
	At each crossing we have a linear equation x

Leo algknt at 04:13, 24 May 2018

2018-05-24T04:13:26Z

← Older revision		Revision as of 00:13, 24 May 2018
Line 3:		Line 3:
	'''Question 1.'''		'''Question 1.'''

	A. Prove that the set of all 3-colourings of a knot diagram is a vector space over {\mathbb F}_3. Hence \lambda(K) is always a power of 3		A. Prove that the set of all 3-colourings of a knot diagram is a vector space over <math>{\mathbb F}_3</math>. Hence <math>\lambda(K)</math> is always a power of 3

	Attempt: Let <math>D</math> be a knot diagram with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in \mathbb{Z}/3\mathbb{Z}</math> represent the arcs. Now let <math>a,b,c \in \mathbb{Z}/3\mathbb{Z}</math> , with		Attempt: Let <math>D</math> be a knot diagram with <math>n</math> crossings. There are <math>n</math> arcs. Let <math>a_1, a_1, \ldots, a_n \in \mathbb{Z}/3\mathbb{Z}</math> represent the arcs. Now let <math>a,b,c \in \mathbb{Z}/3\mathbb{Z}</math> , with


	$
	a\wedge b =		<math>a\wedge b =

	\left\{		\left\{
Line 15:		Line 15:
	c, & a\not= b		c, & a\not= b
	\end{array}		\end{array}
	\right.		\right.</math>
	$

	At each crossing we have a linear equation x		At each crossing we have a linear equation x
Line 23:		Line 22:
	Let		Let

	B. Prove that \lambda(K) is computable in polynomial time in the number of crossings of K.		B. Prove that <math>\lambda(K)</math> is computable in polynomial time in the number of crossings of K.