|
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
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
There is a positive constant such that for any diagram representing the unknot, there is a sequence of at most Reidemeister moves that will convert it to a trivial knot diagram, where is the number of crossings in . A similar result holds for elementary moves on a polygonal knot embedded in the 1-skeleton of the interior of a compact, orientable, triangulated 3-manifold . There is a positive constant such that for each , if consists of tetrahedra and is unknotted, then there is a sequence of at most elementary moves in which transforms to a triangle contained inside one tetrahedron of . We obtain explicit values for and .
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,
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.
|