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.
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
.