## Conjugacy and subgroups of word-hyperbolic groups

Doctoral thesis English OPEN
Buckley, David John
• Subject: QA
arxiv: Mathematics::Group Theory

This thesis describes a number of algorithms and properties relating to Gromov’s\ud word-hyperbolic groups. A fuller outline of the thesis is given, and a number of\ud basic concepts relating to metric spaces, hyperbolicity and automaticity are first\ud briefly detailed in Chapter 1. Chapter 2 then details a solution to the conjugacy\ud problem for lists of elements in a word-hyperbolic group which can be run in linear\ud time; this is an improvement on a quadratic time algorithm for lists which contain\ud an infinite order element. Chapter 3 provides a number of further results and\ud algorithms which build upon this result to efficiently solve problems relating to quasiconvex\ud subgroups of word-hyperbolic groups – specifically, the problem of testing\ud if an element conjugates into a quasiconvex subgroup, and testing equality of double\ud cosets. In Chapter 4, a number of properties of certain coset Cayley graphs are\ud studied, in particular showing that graph morphisms which preserve edge labels and\ud directions and map a quasiconvex subset to a single point also preserve a variety of\ud other properties, for instance hyperbolicity. Finally, Chapter 5 gives a proof that all\ud word-hyperbolic groups are 14-hyperbolic with respect to some generating set.
• References (9)

1 Introduction 1 1.1 A Note on Computational Complexity . . . . . . . . . . . . . . . . 3 1.2 Metric Spaces and Paths . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 X-graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 More about X-words . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Hyperbolicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.6 FSAs, DFAs and Automatic Groups . . . . . . . . . . . . . . . . . 11 1.7 Other Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 The Conjugacy Problem for Lists 17 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 The Infinite Order Case . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.1 Results From [8] . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Finding Long Powers of Infinite Order Elements . . . . . . 25 2.3.3 Conjugating by a Power of a Short-lex Straight Word . . . . 31 2.3.4 Testing Conjugacy by Short-lex Straight Words . . . . . . . 38 2.3.5 Testing Conjugacy of A and B . . . . . . . . . . . . . . . . 41 2.4 Conjugacy of General Lists . . . . . . . . . . . . . . . . . . . . . . 44

4 X-graphs and Hyperbolicity 81 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3 A Tighter Bound on the Thinness of Triangles . . . . . . . . . . . . 86 4.4 Ball Morphisms and Loops . . . . . . . . . . . . . . . . . . . . . . 96 4.5 IB(25δ) implies IB(∞) . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.6 Torsion-free Subgroups have GIB(∞) . . . . . . . . . . . . . . . . . 104 4.7 Geodesic Path Labels Under IB . . . . . . . . . . . . . . . . . . . . 106 4.8 Conclusion and Possible Further Work . . . . . . . . . . . . . . . . 107

[10] Z. Galil. Real-time algorithms for string-matching and palindrome recognition. In Proceedings of the eighth annual ACM symposium on Theory of computing, pages 161-173. ACM New York, NY, USA, 1976.

[11] S.M. Gersten and H.B. Short. Rational subgroups of biautomatic groups. The Annals of Mathematics, 134(1):125-158, 1991.

[12] M. Gromov. Hyperbolic groups. Essays in group theory, 8:75-263, 1987.

[13] D.F. Holt. Word-hyperbolic groups have real-time word problem. International Journal of Algebra and Computation, 10(2):221-228, 2000.

[14] D.F. Holt, B. Eick, and E.A. O'Brien. Handbook of computational group theory. CRC Press, 2005.

[15] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

• Similar Research Results (5)
 Decision problems for word-hyperbolic semigroups (2016) 83% Computation in word-hyperbolic groups (1998) 79% Combinatorial conditions that imply word-hyperbolicity for 3-manifolds (2003) 77% Equivariant covers for hyperbolic groups (2006) 76% Context-free rewriting systems and word-hyperbolic structures with uniqueness (2012) 73%
• Metrics
0
views in OpenAIRE
0
views in local repository
18