TY - JOUR
T1 - Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem
AU - Diekert, Volker
AU - Myasnikov, Alexei G.
AU - Weiß, Armin
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2017/11
Y1 - 2017/11
N2 - 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. Thus, the question arises “how many” such elements there are. This question can be formalized using the notion of strongly generic sets and lower bounds can be proven by applying the theory of amenable graphs. In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G=H⋆AK 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∈A〉, we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A≠H≠φ(A). As application of these characterizations we show that the conjugacy problem in fundamental groups of finite graphs of groups with finitely generated 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 a new proof that the set where the conjugacy problem of the Baumslag group G1,2 is decidable in polynomial time is also strongly generic.
AB - 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. Thus, the question arises “how many” such elements there are. This question can be formalized using the notion of strongly generic sets and lower bounds can be proven by applying the theory of amenable graphs. In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G=H⋆AK 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∈A〉, we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A≠H≠φ(A). As application of these characterizations we show that the conjugacy problem in fundamental groups of finite graphs of groups with finitely generated 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 a new proof that the set where the conjugacy problem of the Baumslag group G1,2 is decidable in polynomial time is also strongly generic.
KW - Amalgamated product
KW - Amenability
KW - Conjugacy problem
KW - Generic case complexity
KW - HNN extension
KW - Schreier graph
UR - http://www.scopus.com/inward/record.url?scp=85006967573&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85006967573&partnerID=8YFLogxK
U2 - 10.1016/j.jsc.2016.11.009
DO - 10.1016/j.jsc.2016.11.009
M3 - Article
AN - SCOPUS:85006967573
SN - 0747-7171
VL - 83
SP - 147
EP - 165
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
ER -