Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 
 

 

Finite generating sets of relatively hyperbolic groups and applications to geodesic languages


Authors: Yago Antolín and Laura Ciobanu
Journal: Trans. Amer. Math. Soc. 368 (2016), 7965-8010
MSC (2010): Primary 20F65, 20F10, 20F67, 68Q45
DOI: https://doi.org/10.1090/tran/6701
Published electronically: March 21, 2016
MathSciNet review: 3546790
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a finitely generated relatively hyperbolic group $ G$, we construct a finite generating set $ X$ of $ G$ such that $ (G,X)$ has the `falsification by fellow traveler property' provided that the parabolic subgroups $ \{H_\omega \}_{\omega \in \Omega }$ have this property with respect to the generating sets $ \{X\cap H_\omega \}_{\omega \in \Omega }$. This implies that groups hyperbolic relative to virtually abelian subgroups, which include all limit groups and groups acting freely on $ \mathbb{R}^n$-trees, or geometrically finite hyperbolic groups have generating sets for which the language of geodesics is regular and the complete growth series and complete geodesic series are rational. As an application of our techniques, we prove that if each $ H_\omega $ admits a geodesic biautomatic structure over $ X\cap H_\omega $, then $ G$ has a geodesic biautomatic structure.

Similarly, we construct a finite generating set $ X$ of $ G$ such that $ (G,X)$ has the `bounded conjugacy diagrams' property or the `neighboring shorter conjugate' property if the parabolic subgroups $ \{H_\omega \}_{\omega \in \Omega }$ have this property with respect to the generating sets $ \{X\cap H_\omega \}_{\omega \in \Omega }$. This implies that a group hyperbolic relative to abelian subgroups has a generating set for which its Cayley graph has bounded conjugacy diagrams, a fact we use to give a cubic time algorithm to solve the conjugacy problem. Another corollary of our results is that groups hyperbolic relative to virtually abelian subgroups have a regular language of conjugacy geodesics.


References [Enhancements On Off] (What's this?)

  • [1] Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR 1744486 (2000k:53038)
  • [2] Martin R. Bridson and James Howie, Conjugacy of finite subsets in hyperbolic groups, Internat. J. Algebra Comput. 15 (2005), no. 4, 725-756. MR 2160576 (2006e:20080), https://doi.org/10.1142/S0218196705002529
  • [3] B. H. Bowditch, Relatively hyperbolic groups, Internat. J. Algebra Comput. 22 (2012), no. 3, 1250016, 66. MR 2922380, https://doi.org/10.1142/S0218196712500166
  • [4] Inna Bumagin, The conjugacy problem for relatively hyperbolic groups, Algebr. Geom. Topol. 4 (2004), 1013-1040. MR 2100689 (2005k:20103), https://doi.org/10.2140/agt.2004.4.1013
  • [5] Inna Bumagin, Time complexity of the conjugacy problem in relatively hyperbolic groups, Internat. J. Algebra Comput. 25 (2015), no. 5, 689-723. MR 3384078, https://doi.org/10.1142/S0218196715500162
  • [6] Laura Ciobanu and Susan Hermiller, Conjugacy growth series and languages in groups, Trans. Amer. Math. Soc. 366 (2014), no. 5, 2803-2825. MR 3165656, https://doi.org/10.1090/S0002-9947-2013-06052-7
  • [7] L. Ciobanu, S. Hermiller, D. F. Holt and S. Rees,
    Conjugacy Languages in Groups,
    preprint, arXiv:1401.7203, Israel Journal of Mathematics, to appear.
  • [8] M. Coornaert, T. Delzant, and A. Papadopoulos, Géométrie et théorie des groupes, Lecture Notes in Mathematics, vol. 1441, Springer-Verlag, Berlin, 1990 (French). Les groupes hyperboliques de Gromov. [Gromov hyperbolic groups]; With an English summary. MR 1075994 (92f:57003)
  • [9] François Dahmani, Combination of convergence groups, Geom. Topol. 7 (2003), 933-963 (electronic). MR 2026551 (2005g:20063), https://doi.org/10.2140/gt.2003.7.933
  • [10] François Dahmani, Finding relative hyperbolic structures, Bull. Lond. Math. Soc. 40 (2008), no. 3, 395-404. MR 2418795 (2010c:20052), https://doi.org/10.1112/blms/bdn018
  • [11] François Dahmani, Existential questions in (relatively) hyperbolic groups, Israel J. Math. 173 (2009), 91-124. MR 2570661 (2011a:20110), https://doi.org/10.1007/s11856-009-0084-z
  • [12] Cornelia Druţu and Mark Sapir, Relatively hyperbolic groups with rapid decay property, Int. Math. Res. Not. 19 (2005), 1181-1194. MR 2147058 (2006d:20077), https://doi.org/10.1155/IMRN.2005.1181
  • [13] Murray J. Elder, Finiteness and the falsification by fellow traveler property, Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part II (Haifa, 2000), 2002, pp. 103-113. MR 1950887 (2003i:20067), https://doi.org/10.1023/A:1021273013372
  • [14] David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694 (93i:20036)
  • [15] David Epstein and Derek Holt, The linearity of the conjugacy problem in word-hyperbolic groups, Internat. J. Algebra Comput. 16 (2006), no. 2, 287-305. MR 2228514 (2008b:20048), https://doi.org/10.1142/S0218196706002986
  • [16] B. Farb, Relatively hyperbolic groups, Geom. Funct. Anal. 8 (1998), no. 5, 810-840. MR 1650094 (99j:20043), https://doi.org/10.1007/s000390050075
  • [17] Rostislav Grigorchuk and Tatiana Nagnibeda, Complete growth functions of hyperbolic groups, Invent. Math. 130 (1997), no. 1, 159-188. MR 1471889 (98i:20038), https://doi.org/10.1007/s002220050181
  • [18] M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75-263. MR 919829 (89e:20070), https://doi.org/10.1007/978-1-4613-9586-7_3
  • [19] Vincent Guirardel, Limit groups and groups acting freely on $ \mathbb{R}^n$-trees, Geom. Topol. 8 (2004), 1427-1470 (electronic). MR 2119301 (2005m:20060), https://doi.org/10.2140/gt.2004.8.1427
  • [20] Susan Hermiller, Derek F. Holt, and Sarah Rees, Star-free geodesic languages for groups, Internat. J. Algebra Comput. 17 (2007), no. 2, 329-345. MR 2310150 (2008g:20066), https://doi.org/10.1142/S0218196707003603
  • [21] Derek F. Holt, Garside groups have the falsification by fellow-traveller property, Groups Geom. Dyn. 4 (2010), no. 4, 777-784. MR 2727663 (2011i:20058), https://doi.org/10.4171/GGD/105
  • [22] Derek F. Holt and Sarah Rees, Artin groups of large type are shortlex automatic with regular geodesics, Proc. Lond. Math. Soc. (3) 104 (2012), no. 3, 486-512. MR 2900234, https://doi.org/10.1112/plms/pdr035
  • [23] Olga Kharlampovich, Alexei Myasnikov, and Denis Serbin, Actions, length functions, and non-Archimedean words, Internat. J. Algebra Comput. 23 (2013), no. 2, 325-455. MR 3038860, https://doi.org/10.1142/S0218196713400031
  • [24] O. Kharlampovich, A. Myasnikov, and P. Weil,
    Completion process and quasi-convex subgroups.
    arXiv: 1408.1917.
  • [25] Urs Lang, Injective hulls of certain discrete metric spaces and groups, J. Topol. Anal. 5 (2013), no. 3, 297-331. MR 3096307, https://doi.org/10.1142/S1793525313500118
  • [26] B. H. Neumann, Groups with finite classes of conjugate subgroups, Math. Z. 63 (1955), 76-96. MR 0072137 (17,234e)
  • [27] Walter D. Neumann and Michael Shapiro, Automatic structures, rational growth, and geometrically finite hyperbolic groups, Invent. Math. 120 (1995), no. 2, 259-287. MR 1329042 (96c:20066), https://doi.org/10.1007/BF01241129
  • [28] W. D. Neumann and M. Shapiro,
    A Short Course in Geometric Group Theory.
    Notes for the ANU Workshop, January/February 1996.
  • [29] Walter D. Neumann and Michael Shapiro, Regular geodesic normal forms in virtually abelian groups, Bull. Austral. Math. Soc. 55 (1997), no. 3, 517-519. MR 1456281 (98f:20017), https://doi.org/10.1017/S0004972700034171
  • [30] Gen. A. Noskov, Growth of certain non-positively curved cube groups, European J. Combin. 21 (2000), no. 5, 659-666. MR 1771984 (2001k:20092), https://doi.org/10.1006/eujc.1999.0372
  • [31] G. A. Noskov, Bounded shortening in Coxeter complexes and buildings, Mathematical structures and modeling, No. 8 (Russian), Omsk. Gos. Univ., Omsk, 2001, pp. 10-14. MR 1890662 (2003a:20064)
  • [32] Z. O'Connor,
    Conjugacy Search Problem for Relatively Hyperbolic Groups,
    preprint, arXiv:1211.5561.
  • [33] D. Osin, Asymptotic dimension of relatively hyperbolic groups, Int. Math. Res. Not. 35 (2005), 2143-2161. MR 2181790 (2006g:20068), https://doi.org/10.1155/IMRN.2005.2143
  • [34] Denis V. Osin, Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems, Mem. Amer. Math. Soc. 179 (2006), no. 843, vi+100. MR 2182268 (2006i:20047), https://doi.org/10.1090/memo/0843
  • [35] Denis V. Osin, Peripheral fillings of relatively hyperbolic groups, Invent. Math. 167 (2007), no. 2, 295-326. MR 2270456 (2008d:20080), https://doi.org/10.1007/s00222-006-0012-3
  • [36] D. Y. Rebbechi,
    Algorithmic Properties of Relatively Hyperbolic Groups,
    PhD Dissertation (2003), Rutgers, Newark.
  • [37] H. Short,
    Groups and combings.
    Preprint, ENS Lyon, 1990.
  • [38] Arto Salomaa and Matti Soittola, Automata-theoretic aspects of formal power series, Texts and Monographs in Computer Science, Springer-Verlag, New York-Heidelberg, 1978. MR 0483721 (58 #3698)
  • [39] Andrew D. Warshall, Deep pockets in lattices and other groups, Trans. Amer. Math. Soc. 362 (2010), no. 2, 577-601. MR 2551498 (2010j:20061), https://doi.org/10.1090/S0002-9947-09-04954-X

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20F65, 20F10, 20F67, 68Q45

Retrieve articles in all journals with MSC (2010): 20F65, 20F10, 20F67, 68Q45


Additional Information

Yago Antolín
Affiliation: Department of Mathematics, Vanderbilt University, 1326 Stevenson Center, Nash- ville, Tennessee 37240
Email: yago.anpi@gmail.com

Laura Ciobanu
Affiliation: Institut de Mathématiques, University of Neuchâtel, R. Emile-Argand 11, CH-2000 Neuchâtel, Switzerland
Email: laura.ciobanu@unine.ch

DOI: https://doi.org/10.1090/tran/6701
Keywords: Relatively hyperbolic groups, Cayley graphs, growth series, conjugacy problem, languages of geodesics, falsification by fellow traveler property, bounded conjugacy diagrams, (bi)automatic groups, rational growth
Received by editor(s): November 6, 2014
Received by editor(s) in revised form: February 4, 2015, and March 3, 2015
Published electronically: March 21, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society