The conjugacy problem for groups of alternating prime tame links is polynomial-time
HTML articles powered by AMS MathViewer
- by Karin Johnsgard PDF
- Trans. Amer. Math. Soc. 349 (1997), 857-901 Request permission
Abstract:
An alternating projection of a prime link can to used to produce a group presentation (of the link group under free product with the infinite cyclic group) with some useful peculiarities, including small cancellation conditions. In this presentation, conjugacy diagrams are shown to have the form of a tiling of squares in the Euclidean plane in one of a limited number of shapes. An argument based on the shape of the link projection is used to show that the tiling requires no more square tiles than a linear function of word length (with constant multiple based on the number of link crossings). It follows that the computation time for testing conjugacy of two group elements (previously known to be no worse than exponential) is bounded by a cubic polynomial. This bounds complexity in the original link group.References
- Kenneth I. Appel, On the conjugacy problem for knot groups, Math. Z. 138 (1974), 273–294. MR 357622, DOI 10.1007/BF01237125
- K. I. Appel and P. E. Schupp, The conjugacy problem for the group of any tame alternating knot is solvable, Proc. Amer. Math. Soc. 33 (1972), 329–336. MR 294460, DOI 10.1090/S0002-9939-1972-0294460-X
- K. I. Appel and P. E. Schupp, Artin groups and infinite Coxeter groups, Invent. Math. 72 (1983), no. 2, 201–220. MR 700768, DOI 10.1007/BF01389320
- Max Dehn, Papers on group theory and topology, Springer-Verlag, New York, 1987. Translated from the German and with introductions and an appendix by John Stillwell; With an appendix by Otto Schreier. MR 881797, DOI 10.1007/978-1-4612-4668-8
- S. M. Gersten and H. B. Short, Small cancellation theory and automatic groups, Invent. Math. 102 (1990), no. 2, 305–334. MR 1074477, DOI 10.1007/BF01233430
- S. M. Gersten and H. Short, Small cancellation theory and automatic groups. II, Invent. Math. 105 (1991), no. 3, 641–662. MR 1117155, DOI 10.1007/BF01232283
- K. Johnsgard, The Structure of the Cayley Complex and a Cubic-time Algorithm for Solving the Conjugacy Problem for Groups of Prime Alternating Knots, Univ. Illinois—Urbana-Champaign: Ph. D. thesis, 1993.
- —, Geometric Tilings for Equal Geodesic Words in $C^{\prime \prime }(p)-T(q)$ Group Presentations, 1993, Preprint.
- I. Kapovitch, Small Cancellation Groups and Translation Numbers, 1993, Preprint.
- Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
- W. Menasco, Closed incompressible surfaces in alternating knot and link complements, Topology 23 (1984), no. 1, 37–44. MR 721450, DOI 10.1016/0040-9383(84)90023-5
- Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
- Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
- Paul E. Schupp, On Dehn’s algorithm and the conjugacy problem, Math. Ann. 178 (1968), 119–130. MR 237620, DOI 10.1007/BF01350654
- Z. Sela, The conjugacy problem for knot groups, Topology 32 (1993), no. 2, 363–369. MR 1217075, DOI 10.1016/0040-9383(93)90026-R
- Friedhelm Waldhausen, The word problem in fundamental groups of sufficiently large irreducible $3$-manifolds, Ann. of Math. (2) 88 (1968), 272–280. MR 240822, DOI 10.2307/1970574
- C. M. Weinbaum, The word and conjugacy problems for the knot group of any tame, prime, alternating knot, Proc. Amer. Math. Soc. 30 (1971), 22–26. MR 279169, DOI 10.1090/S0002-9939-1971-0279169-X
Additional Information
- Karin Johnsgard
- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- Email: karinj@math.cornell.edu
- Received by editor(s): May 26, 1994
- Received by editor(s) in revised form: September 11, 1995
- Additional Notes: The author was supported in part by Alfred P. Sloan Dissertation Fellowship Grant #DD-414.
- © Copyright 1997 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 349 (1997), 857-901
- MSC (1991): Primary 20F10, 03D15, 57M25
- DOI: https://doi.org/10.1090/S0002-9947-97-01617-6
- MathSciNet review: 1351491