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})$.

Question 2 Consider a crossing $X1$ where component 1 is above component 2. If we trace component 1 from $X1$ to another crossing $X2$ with component 1 now below component 2, the $X1$ and $X2$ 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.