Random van Kampen diagrams and algorithmic problems in groups

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In this paper we study the structure of random van Kampen diagrams over finitely presented groups. Such diagrams have many remarkable properties. In particular, we show that a random van Kampen diagram over a given group is hyperbolic, even though the group itself may not be hyperbolic. This allows one to design new fast algorithms for the Word Problem in groups. We introduce and study a new filling function, the depth of van Kampen diagrams, - a crucial algorithmic characteristic of null-homotopic words in the group.

Original languageEnglish
Pages (from-to)121-185
Number of pages65
JournalGroups, Complexity, Cryptology
Volume3
Issue number1
DOIs
StatePublished - May 2011

Keywords

  • Finitely presented groups
  • Hyperbolic diagrams
  • Search algorithms
  • Todd-coxeter algorithm
  • Van Kampen diagram
  • Word Problem

Fingerprint

Dive into the research topics of 'Random van Kampen diagrams and algorithmic problems in groups'. Together they form a unique fingerprint.

Cite this