The conjugacy problem for groups of alternating prime tame links is polynomialtime
Author:
Karin Johnsgard
Journal:
Trans. Amer. Math. Soc. 349 (1997), 857901
MSC (1991):
Primary 20F10, 03D15, 57M25
MathSciNet review:
1351491
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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.
 [A]
Kenneth
I. Appel, On the conjugacy problem for knot groups, Math. Z.
138 (1974), 273–294. MR 0357622
(50 #10090)
 [AS1]
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 0294460
(45 #3530), http://dx.doi.org/10.1090/S0002993919720294460X
 [AS2]
K.
I. Appel and P.
E. Schupp, Artin groups and infinite Coxeter groups, Invent.
Math. 72 (1983), no. 2, 201–220. MR 700768
(84h:20028), http://dx.doi.org/10.1007/BF01389320
 [D]
Max
Dehn, Papers on group theory and topology, SpringerVerlag,
New York, 1987. Translated from the German and with introductions and an
appendix by John Stillwell; With an appendix by Otto Schreier. MR 881797
(88d:01041)
 [GeS1]
S.
M. Gersten and H.
B. Short, Small cancellation theory and automatic groups,
Invent. Math. 102 (1990), no. 2, 305–334. MR 1074477
(92c:20058), http://dx.doi.org/10.1007/BF01233430
 [GeS2]
S.
M. Gersten and H.
Short, Small cancellation theory and automatic groups. II,
Invent. Math. 105 (1991), no. 3, 641–662. MR 1117155
(92j:20030), http://dx.doi.org/10.1007/BF01232283
 [J1]
K. Johnsgard, The Structure of the Cayley Complex and a Cubictime Algorithm for Solving the Conjugacy Problem for Groups of Prime Alternating Knots, Univ. IllinoisUrbanaChampaign: Ph. D. thesis, 1993.
 [J2]
, Geometric Tilings for Equal Geodesic Words in Group Presentations, 1993, Preprint.
 [K]
I. Kapovitch, Small Cancellation Groups and Translation Numbers, 1993, Preprint.
 [LS]
Roger
C. Lyndon and Paul
E. Schupp, Combinatorial group theory, SpringerVerlag,
BerlinNew York, 1977. Ergebnisse der Mathematik und ihrer Grenzgebiete,
Band 89. MR
0577064 (58 #28182)
 [M]
W.
Menasco, Closed incompressible surfaces in alternating knot and
link complements, Topology 23 (1984), no. 1,
37–44. MR
721450 (86b:57004), http://dx.doi.org/10.1016/00409383(84)900235
 [P]
C.
D. Papakyriakopoulos, On Dehn’s lemma and the asphericity of
knots, Ann. of Math. (2) 66 (1957), 1–26. MR 0090053
(19,761a)
 [Scb]
Horst
Schubert, Die eindeutige Zerlegbarkeit eines Knotens in
Primknoten, S.B. Heidelberger Akad. Wiss. Math.Nat. Kl.
1949 (1949), no. 3, 57–104 (German). MR 0031733
(11,196f)
 [Scp]
Paul
E. Schupp, On Dehn’s algorithm and the conjugacy
problem, Math. Ann. 178 (1968), 119–130. MR 0237620
(38 #5901)
 [Se]
Z.
Sela, The conjugacy problem for knot groups, Topology
32 (1993), no. 2, 363–369. MR 1217075
(94g:57012), http://dx.doi.org/10.1016/00409383(93)90026R
 [Wa]
Friedhelm
Waldhausen, The word problem in fundamental groups of sufficiently
large irreducible 3manifolds, Ann. of Math. (2) 88
(1968), 272–280. MR 0240822
(39 #2167)
 [We]
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 0279169
(43 #4895), http://dx.doi.org/10.1090/S0002993919710279169X
 [A]
 K. I. Appel, On the Conjugacy Problem for Knot Groups, Math. Z. 138 (1974), 273294. MR 50:10090
 [AS1]
 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), 329336. MR 45:3530
 [AS2]
 , Artin Groups and Infinite Coxeter Groups, Invent. Math. 72 (1983), 201220. MR 84h:20028
 [D]
 M. Dehn, Papers on Group Theory and Topology, SpringerVerlag, Berlin, 1987. MR 88d:01041
 [GeS1]
 S. M. Gersten and H. Short, Small Cancellation Theory and Automatic Groups, Invent. Math. 102 (1990), 305334. MR 92c:20058
 [GeS2]
 , Small Cancellation Theory and Automatic Groups: Part II, Invent. Math. 105 (1991), 641662. MR 92j:20030
 [J1]
 K. Johnsgard, The Structure of the Cayley Complex and a Cubictime Algorithm for Solving the Conjugacy Problem for Groups of Prime Alternating Knots, Univ. IllinoisUrbanaChampaign: Ph. D. thesis, 1993.
 [J2]
 , Geometric Tilings for Equal Geodesic Words in Group Presentations, 1993, Preprint.
 [K]
 I. Kapovitch, Small Cancellation Groups and Translation Numbers, 1993, Preprint.
 [LS]
 R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, SpringerVerlag, Berlin, 1977. MR 58:28182
 [M]
 W. Menasco, Closed Incompressible Surfaces in Alternating Knot and Link Complements, Topology 23 (1984), 3744. MR 86b:57004
 [P]
 C. D. Papakyriakopoulos, On Dehn's Lemma and the Asphericity of Knots, Ann. of Math. 66 (1957), 126. MR 19:761a
 [Scb]
 H. Schubert, Die eindeutige Zerlegbarkeit eines Knotens in Primknoten, Sitzungsber. Heidelberger Akad. Wiss. Math.Natur. Kl. 1949 (3), 57104. MR 11:196f
 [Scp]
 P. E. Schupp, On Dehn's Algorithm and the Conjugacy Problem, Math. Ann. 178 (1968), 119130. MR 38:5901
 [Se]
 Z. Sela, The Conjugacy Problem for Knot Groups, Topology 32 (1993), 363369. MR 94g:57012
 [Wa]
 F. Waldhausen, The Word Problem in Fundamental Groups of Sufficiently Large Irreducible 3Manifolds, Ann. of Math. 88 (1968), 272280. MR 39:2167
 [We]
 C. Weinbaum, The Word and Conjugacy Problem for the Knot Group of any Tame Prime Alternating Knot, Proc. Amer. Math. Soc. 22 (1971), 2226. MR 43:4895
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (1991):
20F10,
03D15,
57M25
Retrieve articles in all journals
with MSC (1991):
20F10,
03D15,
57M25
Additional Information
Karin Johnsgard
Affiliation:
Department of Mathematics, Cornell University, Ithaca, New York 14853
Email:
karinj@math.cornell.edu
DOI:
http://dx.doi.org/10.1090/S0002994797016176
PII:
S 00029947(97)016176
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 #DD414.
Article copyright:
© Copyright 1997
American Mathematical Society
