Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem

Volker Diekert, Alexei G. Myasnikov, Armin Weiß

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

In various occasions the conjugacy problem in finitely generated amalgamated products and HNN extensions can be decided efficiently for elements which cannot be conjugated into the base groups. This observation asks for a bound on how many such elements there are. Such bounds can be derived using the theory of amenable graphs: In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G = H ∗A K with [H : A] ≥ [K : A] ≥ 2, the Schreier graph with respect to H or K turns out to be non-amenable if and only if [H : A] ≥ 3. Moreover, for an HNN extension of the form G = < H,b | bab-1 = '(a); a 2 A , we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A 6= H 6= '(A). As application of these characterizations we show that under certain conditions the conjugacy problem in fundamental groups of finite graphs of groups with free abelian vertex groups can be solved in polynomial time on a strongly generic set. Furthermore, the conjugacy problem in groups with more than one end can be solved with a strongly generic algorithm which has essentially the same time complexity as the word problem. These are rather striking results as the word problem might be easy, but the conjugacy problem might be even undecidable. Finally, our results yield another proof that the set where the conjugacy problem of the Baumslag group G1;2 is decidable in polynomial time is also strongly generic.

Original languageEnglish
Title of host publicationISSAC 2015 - Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation
Pages141-148
Number of pages8
ISBN (Electronic)9781450334358
DOIs
StatePublished - 24 Jun 2015
Event40th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2015 - Bath, United Kingdom
Duration: 6 Jul 20159 Jul 2015

Publication series

NameProceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
Volume2015-June

Conference

Conference40th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2015
Country/TerritoryUnited Kingdom
CityBath
Period6/07/159/07/15

Keywords

  • Amalgamated product
  • Amenability
  • Conjugacy problem
  • Generic case complexity
  • HNN extension
  • Schreier graph

Fingerprint

Dive into the research topics of 'Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem'. Together they form a unique fingerprint.

Cite this