The number of Reidemeister moves needed for unknotting

Hass, Joel^1, 2 ; Lagarias, Jeffrey³

¹ Department of Mathematics, University of California, Davis, California 95616
² School of Mathematics, Institute for Advanced Study, Princeton, New Jersey 08540
³ AT&T Labs – Research, Florham Park, New Jersey 07932

Journal of the American Mathematical Society, Tome 14 (2001) no. 2, pp. 399-428

Résumé

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

Détail

DOI : 10.1090/S0894-0347-01-00358-7

Bibliographie

[1] Adams, Colin C. The knot book 1994

[2] Avis, David, El-Gindy, Hossam Triangulating point sets in space Discrete Comput. Geom. 1987 99 111

[3] Birman, Joan S., Hirsch, Michael D. A new algorithm for recognizing the unknot Geom. Topol. 1998 175 220

[4] Birman, Joan S., Menasco, William W. Studying links via closed braids. IV. Composite links and split links Invent. Math. 1990 115 139

[5] Burde, Gerhard, Zieschang, Heiner Knots 1985

[6] De Fraysseix, H., Pach, J., Pollack, R. How to draw a planar graph on a grid Combinatorica 1990 41 51

[7] Galatolo, Stefano On a problem in effective knot theory Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. Rend. Lincei (9) Mat. Appl. 1998

[8] Haken, Wolfgang Theorie der Normalflächen Acta Math. 1961 245 375

[9] Hass, Joel Algorithms for recognizing knots and 3-manifolds Chaos Solitons Fractals 1998 569 581

[10] Hass, Joel, Lagarias, Jeffrey C., Pippenger, Nicholas The computational complexity of knot and link problems J. ACM 1999 185 211

[11] Hass, Joel, Scott, Peter Intersections of curves on surfaces Israel J. Math. 1985 90 120

[12] Hempel, John 3-Manifolds 1976

[13] Hopcroft, John, Tarjan, Robert Efficient planarity testing J. Assoc. Comput. Mach. 1974 549 568

[14] Hudson, J. F. P. Piecewise linear topology 1969

[15] Jaco, William, Rubinstein, J. Hyam PL equivariant surgery and invariant decompositions of 3-manifolds Adv. in Math. 1989 149 191

[16] Jaco, William, Tollefson, Jeffrey L. Algorithms for the complete decomposition of a closed 3-manifold Illinois J. Math. 1995 358 406

[17] Murasugi, Kunio Knot theory and its applications 1996

[18] Langer, Rudolph E. The boundary problem of an ordinary linear differential system in the complex domain Trans. Amer. Math. Soc. 1939

[19] Rolfsen, Dale Knots and links 1976

[20] Rourke, Colin Patrick, Sanderson, Brian Joseph Introduction to piecewise-linear topology 1982

[21] Schrijver, Alexander Theory of linear and integer programming 1986

[22] Haken, Wolfgang Theorie der Normalflächen Acta Math. 1961 245 375

[23] Welsh, D. J. A. Complexity: knots, colourings and counting 1993

[24] Nakano, Hidegor㴠Über Abelsche Ringe von Projektionsoperatoren Proc. Phys.-Math. Soc. Japan (3) 1939 357 375

[25] Welsh, D. J. A. Knots and braids: some algorithmic questions 1993 109 123

[26] Nakano, Hidegor㴠Über Abelsche Ringe von Projektionsoperatoren Proc. Phys.-Math. Soc. Japan (3) 1939 357 375