Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(e) ISSN 0894-0347(p)

     

The number of Reidemeister moves needed for unknotting

Author(s): Joel Hass; Jeffrey C. Lagarias
Journal: J. Amer. Math. Soc. 14 (2001), 399-428.
MSC (1991): Primary 57M25; Secondary 11Y16, 68W40
Posted: January 18, 2001
MathSciNet review: 1815217
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract:

There is a positive constant $c_1$ such that for any diagram $\mathcal{D}$ representing the unknot, there is a sequence of at most $2^{c_1 n}$ Reidemeister moves that will convert it to a trivial knot diagram, where $n$ is the number of crossings in $\mathcal{D}$. A similar result holds for elementary moves on a polygonal knot $K$ embedded in the 1-skeleton of the interior of a compact, orientable, triangulated $PL$ 3-manifold $M$. There is a positive constant $c_2$ such that for each $t \geq 1$, if $M$ consists of $t$ tetrahedra and $K$ is unknotted, then there is a sequence of at most $2^{c_2 t}$ elementary moves in $M$ which transforms $K$ to a triangle contained inside one tetrahedron of $M$. We obtain explicit values for $c_1$ and $c_2$.


References:

1.
C. Adams, The Knot Book. An elementary introduction to the mathematical theory of knots, W. H. Freeman, New York, 1994. MR 94m:57007

2.
J. W. Alexander and G. B. Briggs, On types of knotted curves, Ann. Math., 28 (1926/27), 562-586.

3.
D. Avis and H. El Gindy, Triangulating point sets in space, Disc. & Comp. Geom., 2 (1987), 99-111. MR 88h:68082

4.
J. Birman and M.D. Hirsch, Recognizing the unknot, Geom. Topol., 2 (1998), 175-220. MR 2000a:57005

5.
J. Birman and W. Menasco, Studying links via closed braids V: The unlink, Trans. AMS, 329 (1992), 585-606. MR 92g:57010b

6.
G. Burde and H. Zieschang, Knots, de Gruyter, 1985. MR 87b:57004

7.
H. de Fraysseix, J. Pach and R. Pollack, How to draw a planar graph on a grid, Combinatorica, 10 (1990), 41-51. MR 91g:05123

8.
S. Galatolo, On a problem in effective knot theory, Rendiconti dell Accademia dei Lincei, 9 (1999), no. 4, 299-306. MR 2000j:57010

9.
L. Goeritz, Bemerkungen zur knotentheorie, Abh. Math. Sem. Univ. Hamburg, 10 (1934), 201-210.

10.
W. Haken, Theorie der Normalflachen, ein Isotopie Kriterium für ein Kreis, Acta Math., 105 (1961), 245-375. MR 25:4519a

11.
J. Hass, Algorithms for recognizing knots and 3-manifolds, Chaos, Fractals and Solitons, 9 (1998), 569-581. MR 2000a:57038

12.
J. Hass, J. C. Lagarias and N. Pippenger, The computational complexity of knot and link problems, J. Assoc. Comp. Mach., 46 (1999), 185-211. MR 2000g:68056

13.
J. Hass, J. C. Lagarias and N. Pippenger, The computational complexity of knot and link problems, preliminary report, Proc. 38th Annual Symposium on Foundations of Computer Science, (1997), 172-181.

14.
J. Hass and G. P. Scott, Intersections of curves on surfaces, Israel J. Math., 51 (1985), 90-120. MR 86k:57007

15.
J. Hempel, 3-Manifolds, Princeton University Press, Princeton, NJ, 1976. MR 54:3702

16.
J. E. Hopcroft and R. E. Tarjan, Efficient planarity testing, J. Assoc. Comp. Mach., 21 (1974), 549-568. MR 50:11841

17.
J.F.P. Hudson, Piecewise-Linear Topology, W.A. Benjamin Inc., 1969. MR 40:2094

18.
W. Jaco and H. Rubinstein,$PL$ equivariant surgery and invariant decompositions of 3-manifolds, Advances in Math., 73 (1989), 149-191. MR 90g:57016

19.
W. Jaco and J. L. Tollefson, Algorithms for the complete decomposition of a closed 3-manifold, Illinois J. Math., 39 (1995), 358-406. MR 97a:57014

20.
H. Kneser, Geschlossene Flachen in dreidimensionalen Mannigfaltigkeiten, Jahresbericht Math. Verein., 28 (1929), 248-260.

21.
K. Murasugi, Knot Theory and Its Applications, Birkhauser, Boston, MA, 1996. MR 97g:57011

22.
H. Reidemeister, Knoten und Gruppen, Abh. Math. Sem., Univ. Hamburg, 5 (1926), 7-23.

23.
H. Reidemeister, Elementare Begründang der Knotentheorie, Abh. Math. Sem. Univ. Hamburg, 5 (1926), 24-32.

24.
H. Reidemeister, Knotentheorie, Springer, Berlin, 1932; Chelsea, New York, 1948. (English translation: Knot Theory, BCS Associates, Moscow, ID, 1984. MR 84j:57005)

25.
D. Rolfsen, Knots and Links, Publish or Perish Inc., Berkeley, CA, 1976. MR 58:24236

26.
C.P. Rourke and B.J. Sanderson, Introduction to Piecewise-Linear Topology, Springer-Verlag, Berlin, Heidelberg, New York, 1982. MR 83g:57009

27.
A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, New York, 1986. MR 88m:90090

28.
H. Schubert, Bestimmung der Primfactor zerlegung von Verkettungen, Math. Z., 76 (1961), 116-148. MR 25:4519b

29.
A. Sebö, Hilbert bases, Caratheodory's theorem and combinatorial optimization, in Integer Programming and Combinatorial Optimization, R. Kannan and W. R. Pulleybank, Eds., U. Waterloo Press, 1990, 431-455.

30.
D. J. A. Welsh, Complexity: Knots, Colourings and Counting, Cambridge University Press, Cambridge, 1993. MR 94m:57027

31.
D. J. A. Welsh, The complexity of knots, in Quo Vadis, Graph Theory?, J. Gimbel, J. Kennedy and L. V. Quintoo, eds., North-Holland, Amsterdam, 1993, 159-173. (Also: Annals Disc. Math., 55 (1993), 159-173. MR 94c:57021)

32.
D. J. A. Welsh, Knots and braids: some algorithmic questions, in Graph Structure Theory, Seattle, WA, 1991, Contemporary Math., Vol. 147, AMS, Providence, RI, 1993, 109-123. MR 94g:57014

33.
F. Y. Wu, Knot Theory and Statistical Mechanics, Rev. Mod. Phys., 64 (1992), 1099-1131. MR 94f:82025a; erratum MR 94f:82025b


Similar Articles:

Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 57M25, 11Y16, 68W40

Retrieve articles in all Journals with MSC (1991): 57M25, 11Y16, 68W40


Additional Information:

Joel Hass
Affiliation: Department of Mathematics, University of California, Davis, California 95616
Address at time of publication: School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
Email: hass@math.ucdavis.edu

Jeffrey C. Lagarias
Affiliation: AT&T Labs -- Research, Florham Park, New Jersey 07932
Email: jcl@research.att.com

DOI: 10.1090/S0894-0347-01-00358-7
PII: S 0894-0347(01)00358-7
Keywords: Knot theory, knot diagram, Reidemeister move, normal surfaces, computational complexity
Received by editor(s): May 8, 1998
Received by editor(s) in revised form: October 10, 2000
Posted: January 18, 2001
Additional Notes: The first author was partially supported by NSF grant DMS-9704286.
This paper grew out of work begun while the authors were visiting the Mathematical Sciences Research Institute in Berkeley in 1996/97. Research at MSRI was supported in part by NSF grant DMS-9022140.
Copyright of article: Copyright 2001, AT&T Corp.




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia