User:Leo algknt

Home Work 1

Question 1.

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

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

[math]\displaystyle{ a\wedge b = \left\{ \begin{array}{cc} a, & a = b\\ c, & a\not= b \end{array} \right. }[/math], so that [math]\displaystyle{ a\wedge b + a + b \equiv 0\mod 3 }[/math].

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

B. Prove that [math]\displaystyle{ \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]\displaystyle{ M }[/math] (M is a result of [math]\displaystyle{ n }[/math] linear equations coming from [math]\displaystyle{ 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]\displaystyle{ \lambda(K) }[/math].