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 ${\mathbb {Z} }_{3}$. Hence $\lambda (K)$ is always a power of 3.

Attempt: Let $D$ be a knot diagram for the knot $K$ with $n$ crossings. There are $n$ arcs. Let $a_{1},a_{1},\ldots ,a_{n}\in {\mathbb {Z} }_{3}$ represent the arcs. Now let $a,b,c\in {\mathbb {Z} }_{3}$. Define $\wedge :{\mathbb {Z} }_{3}\times {\mathbb {Z} }_{3}\rightarrow {\mathbb {Z} }_{3}$ by

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

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

B. Prove that $\lambda (K)$ is computable in polynomial time in the number of crossings of K.

Atempt 1: From Part A, we can compute the rank of the $M$ (M is a result of $n$ linear equations coming from $n$ 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 $\lambda (K)$.

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