Home Work 1
Question 1.
A. Prove that the set of all 3-colourings of a knot diagram is a vector space over
. Hence
is always a power of 3.
Attempt: Let
be a knot diagram for the knot
with
crossings. There are
arcs. Let
represent the arcs. Now let
. Define
by
,
so that
.
Then, with the above definition, we get a linear equation
for each each of the
crossings, where
. Thus we get a system of
linear equation, from which we get a matrix
. The nullspace
of
is the solution to this system of equation and this is exactly the set of all 3-colourings of
. This is a vector space of size
B. Prove that
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 is a result of
linear equations coming from
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
.
Attempt 2: The time complexity for looping through
crossing is
. Now at each of the
crossing, three arcs meet and deciding which of the three colours to colour them is also of complexity
.