Skip Navigation


Journal of Topology Advance Access originally published online on August 17, 2009
Journal of Topology 2009 2(3):442-460; doi:10.1112/jtopol/jtp018
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Crisp, J.
Right arrow Articles by Wiest, B.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© 2009 London Mathematical Society

The conjugacy problem in subgroups of right-angled Artin groups

John Crisp

Institut de Mathématiques de Bourgogne, CNRS UMR 5584, Université de Bourgogne, B.P. 47870, 21078 Dijon cedex, France jcrisp@gmail.com

Eddy Godelle

Laboratoire de Mathématiques, Nicolas Oresme, CNRS UMR 6139, Université de Caen, 14032 Caen cedex, France eddy.godelle@math.unicaen.fr

Bert Wiest

IRMAR, CNRS UMR 6625, Campus de Beaulieu, Université de Rennes 1, 35042 Rennes, France bertold.wiest@univ-rennes1.fr

We prove that the conjugacy problem in a large and natural class of subgroups of right-angled Artin groups can be solved in linear time. This class of subgroups has been previously studied by Crisp and Wiest, and independently by Haglund and Wise, as fundamental groups of compact special cube complexes.

Received April 1, 2008.

2000 Mathematics Subject Classification 20F10, 20F36, 20F65

This work was financially supported by the ACI JC1041 of the CNRS.



References

  1. Abrams A. Configuration spaces of colored graphs. Geom. Dedicata (2002) 92:185–194.[CrossRef]
  2. Abrams A., Ghrist R. Finding topology in a factory: configuration spaces. Amer. Math. Monthly (2002) 109(2):140–150.[CrossRef]
  3. Abrams A., Ghrist R. State complexes for metamorphic robots. Internat. J. Robot. Res. (2004) 23(7-8):809–824.
  4. Aho A. V., Hopcroft J. E., Ullman J. D. The design and analysis of computer algorithms (1974) London: Addison-Wesley.
  5. Baudisch A. Subgroups of semifree groups. Acta Math. Acad. Sci. Hungar (1981) 38:19–28.[CrossRef]
  6. Boyer R. S., Moore J. S. A fast string searching algorithm. Commun. ACM (1977) 20(10):762–772.[CrossRef]
  7. Bridson M. R., Haefliger A. Metric spaces of non-positive curvature (1999) 319. Berlin: Springer. Springer Grundlehren Series.
  8. Cartier P., Foata D. Problèmes combinatoires de commutation et réarrangements (1969) 85. Berlin–New York: Springer. Lecture Notes in Mathematics.
  9. Charney R. An introduction to right-angled Artin groups. Geom. Dedicata (2007) 125:141–158.[CrossRef]
  10. Crisp J., Wiest B. Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups. Algebr. Geom. Topol. (2004) 4:439–472.[CrossRef]
  11. Crisp J., Wiest B. Quasi-isometrically embedded subgroups of braid and diffeomorphism groups. Trans. Amer. Math. Soc. (2007) 359:5485–5503.[CrossRef]
  12. Duboc C. Commutation dans les monoïdes libres, un cadre théorique pour l'étude du parallélisme. (1986) Doctoral thesis, University of Rouen, Rouen.
  13. Epstein D. B. A., Holt D. The linearity of the conjugacy problem in word-hyperbolic groups. Internat. J. Algebra Comput. (2006) 16(2):287–305.[CrossRef]
  14. Farley D., Sabalka L. Discrete Morse theory and graph braid groups. Algebr. Geom. Topol. (2005) 5:1075–1109.[CrossRef]
  15. Farley D., Sabalka L. On the cohomology rings of tree braid groups. J. Pure Appl. Algebra (2008) 212:53–71.[CrossRef]
  16. Ghrist R., Peterson V. The geometry and topology of reconfiguration. Adv. Appl. Math. (2007) 38:302–323.[CrossRef]
  17. Gusfield D. Algorithms on strings, trees, and sequences: computer science and computational biology (1997) Cambridge: Cambridge University Press.
  18. Haglund F., Wise D. Special cube complexes. Geom. Funct. Anal. (2008) 17(5):1551–1620.[CrossRef]
  19. Haglund F., Wise D. Coxeter groups are special. (2008) Preprint.
  20. Knuth D. E, Morris J. H., Pratt V. R. Fast pattern-matching algorithms. SIAM J. Comput. (1977) 6(2):323–350.[CrossRef]
  21. Krob D., Mairesse J., Michos I. Computing the average parallelism in trace monoids. Discrete Math. (2003) 273:131–162.[CrossRef]
  22. Lalonde P. Contribution à l'étude des empilements. (1990) Doctoral thesis, University of Quebec and Montreal, Montreal.
  23. Liu H.-N., Wrathall C., Zeger K. Efficient solution of some problems in free partially commutative monoids. Inform. and Comput. (1990) 89:180–198.[CrossRef]
  24. Niblo G., Reeves L. The geometry of cube complexes and the complexity of their fundamental groups. Topology (1998) 37:621–633.[CrossRef][Web of Science]
  25. Sabalka L. Embedding right-angled Artin groups into graph braid groups. Geom. Dedicata (2007) 124:191–198.[CrossRef]
  26. Servatius H. Automorphisms of graph groups. J. Algebra (1987) 126:34–60.
  27. Stephen G. String searching algorithms (1994) River Edge: World Scientific.
  28. Van Wyk L. Graph groups are biautomatic. J. Pure Appl. Algebra (1994) 94:341–352.[CrossRef]
  29. Viennot X. Algèbres de Lie libre et monoïdes libres (1978) 691. Berlin: Springer. Lecture Notes in Mathematics.
  30. Wrathall C. Free partially commutative groups. In: Combinatorics, computing and complexity—Du D.Z., Hu G., eds. Norwell, MA, 1989: Kluwer Academic/Science Press.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Crisp, J.
Right arrow Articles by Wiest, B.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?