Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

   
 
 

 

The number of Reidemeister moves needed for unknotting


Authors: Joel Hass and Jeffrey C. Lagarias
Journal: J. Amer. Math. Soc. 14 (2001), 399-428
MSC (1991): Primary 57M25; Secondary 11Y16, 68W40
DOI: https://doi.org/10.1090/S0894-0347-01-00358-7
Published electronically: January 18, 2001
MathSciNet review: 1815217
Full-text PDF

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 [Enhancements On Off] (What's this?)

  • 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: https://doi.org/10.1090/S0894-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
Published electronically: 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.
Article copyright: © Copyright 2001 AT&T Corp.

American Mathematical Society