Time complexity of the conjugacy problem in relatively hyperbolic groups.

DOI10.1142/S0218196715500162MaRDI QIDQ2942798zbMATH OpenFDO

Authors Inna Bumagin

Publication date 11 September 2015

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.4528

zbMATH Keywords

algorithmic problemsconjugacy problemconjugacy search problemrelatively hyperbolic groupstime complexity

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Hyperbolic groups and nonpositively curved groups (20F67) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: If $u$ and $v$ are two conjugate elements of a hyperbolic group then the length of a shortest conjugating element for $u$ and $v$ can be bounded by a linear function of the sum of their lengths, as was proved by Lysenok. Bridson and Haefliger showed that in a hyperbolic group the conjugacy problem can be solved in polynomial time. We extend these results to relatively hyperbolic groups. In particular, we show that both the conjugacy problem and the conjugacy search problem can be solved in polynomial time in a relatively hyperbolic group, whenever the corresponding problem can be solved in polynomial time in each parabolic subgroup. We also prove that if $u$ and $v$ are two conjugate hyperbolic elements of a relatively hyperbolic group then the length of a shortest conjugating element for $u$ and $v$ is linear in terms of their lengths.

Recommendations

• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• The conjugacy problem in hyperbolic groups for finite lists of group elements.
• The conjugacy problem for relatively hyperbolic groups.
• Permute and conjugate: the conjugacy problem in relatively hyperbolic groups
• CONJUGACY OF FINITE SUBSETS IN HYPERBOLIC GROUPS

Cites work

• \(\mathbb Z^n\)-free groups are \(\mathrm{CAT}(0)\).
• A COMBINATION THEOREM FOR RELATIVELY HYPERBOLIC GROUPS
• A topological characterisation of relatively hyperbolic groups
• Actions of finitely generated groups on \(\mathbb{R}\)-trees.
• Artin groups of extra-large type are biautomatic
• Combination of convergence groups.
• Conjugacy in normal subgroups of hyperbolic groups.
• CONJUGACY OF FINITE SUBSETS IN HYPERBOLIC GROUPS
• Diophantine geometry over groups. I: Makanin-Razborov diagrams
• Finding relative hyperbolic structures
• Hadamard spaces with isolated flats. (With an appendix written jointly with Mohamad Hindawi).
• HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
• Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups
• LIMIT GROUPS ARE CAT(0)
• Polynomial time conjugacy in wreath products and free solvable groups.
• Presenting parabolic subgroups.
• Relative hyperbolicity and relative quasiconvexity for countable groups.
• Relatively hyperbolic groups
• Relatively hyperbolic groups, rapid decay algebras, and a generalization of the Bass conjecture
• Relatively hyperbolic groups.
• Subgroups of small Cancellation Groups
• The conjugacy problem for relatively hyperbolic groups.
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• The word and geodesic problems in free solvable groups.

Cited in

(16)

• Deciding isomorphy using Dehn fillings, the splitting case
• The conjugacy problem for relatively hyperbolic groups.
• The compressed word problem in relatively hyperbolic groups
• Finite generating sets of relatively hyperbolic groups and applications to geodesic languages
• The conjugacy problem in hyperbolic groups for finite lists of group elements.
• A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups
• Permute and conjugate: the conjugacy problem in relatively hyperbolic groups
• Linear time algorithm for the conjugacy problem in the first Grigorchuk group
• Logspace and compressed-word computations in nilpotent groups
• The conjugacy problem in the Grigorchuk group is polynomial time decidable.
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
• Bounded conjugators for real hyperbolic and unipotent elements in semisimple Lie groups
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• CONJUGACY OF FINITE SUBSETS IN HYPERBOLIC GROUPS
• Conjugator lengths in hierarchically hyperbolic groups
• The compressed conjugacy problem in relatively hyperbolic groups

This page was built for publication: Time complexity of the conjugacy problem in relatively hyperbolic groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942798)