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)
  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    18
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Warwick Research Archives Portal Repository - IRUS-UK 0 18
Share - Bookmark