-Up to-Home/Maths/Knot Theory
-Site Map|-Text version

- Unknot Equivalence

  [Fred Curtis - Feb-May 2001]
These working notes were motivated by my horror at the described length and complexity of Haken's 1961 unknot-equivalence algorithm in [Adams94]. [Hass99] indicates no known non-trivial lower bounds to the complexity of the problem at the time of writing.

[Synopsis] [Chronology / Working] [References]

Synopsis

Deciding if a given knot diagram is the unknot, i.e. deciding if the diagram can be untangled into a simple loop, is part of the harder, more general task of deciding if two knot diagrams represent the same knot.
Let U0 denote the trivial (0-crossing) diagram of the unknot.

Let +I denote addition of a crossing to a knot diagram by a type I Reidemeister move. Let -I denote removal of a crossing by a type I move. Similarly, let +II (-II) denote addition (removal) of a pair of crossings by a type II Reidemeister move. Let III denote a type III Reidemeister move.

For a knot diagram D, let D|m denote the set of the diagrams which may result when a move m is applied to D. Let D|M denote the set of the diagrams which may result when a move from the set M is applied to D. Let D|M* denote the set of diagrams which may result when a finite sequence of moves from the set M is applied to D. Examples: all possible diagrams of a knot with diagram K may be written as K|{+I,-I,+II,-II,III}* ; this page is largely concerned with the set of all unknot diagrams U0|{+I,-I,+II,-II,III}*.

Write a particular element of D|M* as D|t1|...|tn to mean the result of applying transformations t1,...,tn to D. Each transformation ti consists of a move mi from M plus information to describe where in D|t1|...|ti-1 the move mi should be applied.

Principle of Move Transposition (PMT) : If a diagram D|...|T1|T2|... contains two adjacent transformation sequences T1 and T2 which change disjoint regions then the diagram is unchanged by transposing T1 and T2, i.e. D|...|T1|T2|... = D|...|T2|T1|...

U0, the trivial diagram
of the unknot
knot:(63214789)
Type I Reidemeister Move
-
Type II Reidemeister Move
-
Type III Reidemeister Move
-

Theorem 1: U0|{+I}* = U0|{+I,-I}*     [proof]

Theorem 2: U0|{+II}* = U0|{+II,-II}*     [proof]

The predicate ArbReduce0 captures the reduction of a diagram to U0 by successive removal of crossings via arbitrary moves from a set M. Define ArbReduce0(S, M) for a set M of crossing-removal moves to mean for any diagram D in the set S,

Theorem 1 implies ArbReduce0(U0|{+I}*, {-I}).

Theorem 2 implies ArbReduce0(U0|{+II}*, {-II}).

Conjecture 6 : ArbReduce0(U0|{+II}*, {-I,-II})

Chronology / Working

Assorted Unknot diagrams
A Nasty Unknot - Based on
Fig 1.29 from [Adams94]
knot:(66997'17'886~662217'133'668888888441'2268~87442222222)
Goeritz's unknot
knot:(63'13'3'11'36887'9888413'11'331'4889'7888)
The Monster - Based on file
'monster-init.kps' from [KnotPlot]
knot:(2222669'666~68444444888866662~224448~86666222~222444448~86368~8~8~8444~4)
Cousin It - Based on file
'ks-init.kps' from [KnotPlot]
knot:(88~8~8~88842~2~266684~4~4442226666624~4~4444888886666~6~662224444488~8~886662222~2~2~2222~2~2~222244488~8~886666622244~4~4444888886666~6~6244444222666~6~684442~2~26888~8~8~88)
Nemesis - An unknot of Thistlethwaite
knot:(666~6~66888844442~266622~24~4~4222~26666688~8888884442~222244~488~888662~2222~26666624~44444448888)

9th Feb 2001

11th Feb 2001

  • Formulated conjecture 1 : a -I, -II or -IIcontrived move can be applied to any unknot diagram with crossings. [proved false by counter-example - e.g. The Monster]
  • Read [Hayes97] - complexity of current unknot-equivalence algorithms still seems to be around O(2n) for a diagram with n crossings.
-IIcontrived move
-

12th Feb 2001

13th Feb 2001

14th Feb 2001

16th Feb 2001

17th Feb 2001

19th Feb 2001

20th Feb 2001

21st Feb 2001

22nd Feb 2001

23rd Feb 2001

26th Feb 2001

28th Feb 2001

Early Mar 2001

18th Mar 2001

13th Apr 2001

18th Apr 2001

Early May 2001

22nd May 2001

8th Dec 2001

Untangling the Monster with a series of -R moves
1:
knot:(2~224448~86666222~222444448~86368~8~8~8444~42222669'666~68*44444488886666)(-662222)		2:
knot:(*666~688888442~2244*48~86666222~222444448~86368~8~8~8444~42222669')(-88)		3:
knot:222(*8~86666222~222444448~8*6368~8~8~8444~42222669'884)(-422)		4:
knot:222(4226368~8~8~8444~42222669'884)
Untangling Cousin It
knot:(88~8~8~88842~2~266684~4~44422266666*24~4~444488888*6666~6~662224444488~8~886662222~2~2~22)688(-66888888844444444222)knot:(88~8~8~88842~2~266684~4~444*22266666668888888444444442226*666~6~662224444488~8~886662222~2~2~22)444488888(-8)knot:(88~8~8~88842~2~266684~4~4448666~6~66*222444448*8~8~886662222~2~2~22)66888888(-88844444442222266)knot:(88~8~8~88842~2~266684~4~4448666~6~6*6888444444422222668~8~886662*222~2~2~22)6888888(-84)
knot:(88~8~8~88842~2~2*6668*4~4~4448666~6~684222~2~2~22)448888(-444888866666662224)knot:(88~8~8~888*42~2~244488886666*66622244~4~4448666~6~684222~2~2~22)48888888(-8)knot:(88~8~8~888*866622244~4~444866*6~6~684222~2~2~22)48888888(-42)knot:(88~8~8~888*426~6~684*222~2~2~22)48888888(-6)8
Untangling Goeritz' unknot
knot:(63'13'3'11'36887'9888413'11'33*1'4889*'7888)2223(-3~2)knot:(63'13'3'11'36887'*988841*3'11'338~777886)3(-133)knot:(8~77788663'13'3'11'36887'7793'1~1*33)(-14888)knot:(*36887*'7793'1~1'222698~77788663'13'311)(-89')
knot:(*1~1'2222266988~7*7778886663'13'3311118889'77993'1)(-321)knot:(*3'3311118889'77*993'13217778886663'1)(-14)knot:(14993'13217778886663'1)
Untangling Nemesis
knot:(*2~24~4~4*222~26666688~8888884442~222244~488~888662~2222~26666624~44444448888666~6~66888~844442~26662)(-4~4~42~2)knot:(*2~2222~2*6666688~8888884442~222244~488~8~88662~2222~26666624~44444448888666~6~66888~844442~266624~4~4)(-444222222666)knot:(66624~4~44442222226666666688~8888884442~222244~488~8~88662~2222~26666624~4444444888866*6~6~66888~844442~2*)(-2~2)knot:(66624~4~44442222226666666688~8888884442~222244~488~8~88662~2222~26666624~44444448888668~8)knot:(*4488~8~8886662~2*2222~26666624~444444448888668~886666224~4~4444422222266666666688~88888884442~2222244)(-888~86)
knot:(*4~444444448888668~88*6666224~4~4444422222266666666688~88888884442~2222244888~862222~2666662)(-22444444444448888888886666)knot:(*666222444444444448888888886666666622*4~4~4444422222266666666688~88888884442~2222244888~862222~266)(-8888)knot:(*44422222266666666688~88888884442~2222244*888~862222~26688884~4~44)(-2226)knot:(2226888~862222~26688884~4~44)

References

-This page
last changed:
22 May 2003
[Validate HTML]
-Donate free
food & land		 
-
|Feedback by email
or Web form