Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T15:44:31.945Z Has data issue: false hasContentIssue false
  • English
  • Français

Counting subgraphs in fftp graphs with symmetry

Part of: Combinatorics Special aspects of infinite or finite groups

Published online by Cambridge University Press:  27 November 2019

YAGO ANTOLÍN
YAGO ANTOLÍN*
Affiliation:
Departamento de Matemáticas, Facultad de Ciencas, Universidad Autónoma de Madrid Cantoblanco, Ciadad Universitaria, 28049 Madrid, Spain Instituto de Ciencias Matemáticas, Madrid, Spain. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Following ideas that go back to Cannon, we show the rationality of various generating functions of growth sequences counting embeddings of convex subgraphs in locally-finite, vertex-transitive graphs with the (relative) falsification by fellow traveler property (fftp). In particular, we recover results of Cannon, of Epstein, Iano–Fletcher and Zwick, and of Calegari and Fujiwara. One of our applications concerns Schreier coset graphs of hyperbolic groups relative to quasi-convex subgroups, we show that these graphs have rational growth, the falsification by fellow traveler property, and the existence of a lower bound for the growth rate independent of the finite generating set and the infinite index quasi-convex subgroup.

MSC classification

Primary: 20F67: Hyperbolic groups and nonpositively curved groups
Secondary: 05A15: Exact enumeration problems, generating functions
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 170 , Issue 2 , March 2021 , pp. 327 - 353
Copyright
© Cambridge Philosophical Society 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Antolín, Y. and Ciobanu, L.. Finite generating sets of relatively hyperbolic groups and applications to geodesic languages, Trans. Amer. Math. Soc. 368 (2016), no. 11, 7965–8010.CrossRefGoogle Scholar
Bourbaki, N.. Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines. Actualités Scientifiques et Industrielles, no. 1337 (Hermann, Paris, 1968).Google Scholar
Bridson, M. and Haefliger, A.. Metric spaces of non-positive curvature. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 319 (Springer-Verlag, Berlin, 1999), xxii+643 pp.CrossRefGoogle Scholar
Calegari, D. and Fujiwara, K.. Counting subgraphs in hyperbolic graphs with symmetry. J. Math. Soc. Japan 67 (2015), no. 3, 1213–1226.CrossRefGoogle Scholar
Chatterji, I., Drutu, C. and Haglund, F.. Kazhdan and Haagerup properties from the median viewpoint. Adv. Math. 225 (2010), no. 2, 882–921.CrossRefGoogle Scholar
Chepoi, V.. Graphs of some CAT(0) complexes. Adv. in Appl. Math. 24 (2000), no. 2, 125–179.CrossRefGoogle Scholar
Coornaert, M., Delzant, T. and Papadopoulos, A.. Geometrie et theorie des groupes. Lecture Notes in Math., vol.1441 (Springer Verlag, 1990).CrossRefGoogle Scholar
Davis, M W.. The geometry and topology of Coxeter groups. London Mathematical Society Monographs Series, 32 (Princeton University Press, Princeton, NJ, 2008).Google Scholar
Cannon, J. W.. The combinatorial structure of cocompact discrete hyperbolic groups. Geom. Dedicata 16 (1984), 123–148.CrossRefGoogle Scholar
Elder, M.. Finiteness and the falsification by fellow traveler property. Geom. Dedicata 95 (2002), 103–113.CrossRefGoogle Scholar
Elder, M.. Regular languages and the falsification by fellow traveler property. Algebraic and Geometric Topology 5 (2005), paper no. 8, pages 129–134.CrossRefGoogle Scholar
Elvey–Price, A.. A Cayley graph for F 2 × F 2 which is not minimally almost convex. arXiv:1611.00101.Google Scholar
Epstein, D. B. A., Cannon, J., Holt, D., Levy, S., Paterson, M. and Thurston, W.. Word Processing in Groups (Jones and Bartlett, Boston, 1992).CrossRefGoogle Scholar
Epstein, D. B. A., Iano–Fletcher, A. R. and Zwick, U.. Growth functions and automatic groups. Experiment. Math. 5 (1996), no. 4, 297–315.CrossRefGoogle Scholar
Eskin, A., Fisher, D. and Whyte, K.. Coarse differentiation of quasi-isometries I: spaces not quasi-isometric to Cayley graphs. Ann. of Math. (2) 176 (2012), no. 1, 221–260.CrossRefGoogle Scholar
Dahmani, F., Futer, D. and Wise, D. T.. Growth of quasiconvex subgroups. Math. Proc. Camb. Phil. Soc. to appear doi:10.1017/S0305004118000440.CrossRefGoogle Scholar
Hsu, T. and Wise, D. T.. Separating quasiconvex subgroups of right-angled Artin groups. Math. Z. 240 (2002), no. 3, 521–548.CrossRefGoogle Scholar
Gromov, M.. Hyperbolic groups. Essays in group theory. Math. Sci. Res. Inst. Publ., 8, (Springer, New York, 1987), 75–163.Google Scholar
Holt, D. F.. Garside groups have the falsification by fellow-traveler property. Groups Geom. Dyn. 4 (2010), 777–784.CrossRefGoogle Scholar
Holt, D. F. and Rees, S.. Artin groups of large type are shortlex automatic with regular geodesics. Proc. Lond. Math. Soc. (3) 104 (2012), no. 3, 486–512.CrossRefGoogle Scholar
Kapovich, I.. The nonamenability of Schreier graphs for infinite index quasiconvex subgroups of hyperbolic groups. Enseign. Math. (2) 48 (2002), no. 3-4, 359–375.Google Scholar
Koubi, M.. Croissance uniforme dans les groupes hyperboliques. Ann. Inst. Fourier (Grenoble) 48 (1998), no. 5, 1441–1453.CrossRefGoogle Scholar
Loeffler, J., Meier, J. and Worthington, J.. Graph products and Cannon pairs. Internat. J. Algebra Comput. 12 (2002), 6, 747–754.CrossRefGoogle Scholar
Neumann, W. D. and Shapiro, M.. Automatic structures, rational growth, and geometrically finite hyperbolic groups. Invent. Math. 120 (1995), no. 2, 259–287.CrossRefGoogle Scholar
Noskov, G. A.. Growth of certain non-positively curved cube groups. Europ. J. Combinatorics 21 (2000), 659–666.CrossRefGoogle Scholar
Noskov, G. A.. Bounded shortening in Coxeter complexes and buildings. pp. 10–14 in: Guts, A. K. (Ed.), Mathematical structures and modeling, no. 8 (Omsk. Gos. Univ., Omsk 2001). Available electronically at http://cmm.univer.omsk.su/sbornik/sborn8.html.Google Scholar
Osin, D.. Relatively hyperbolic groups: intrinsic geometry, algebraic properties and algorithmic problems. Mem. Amer. Math. Soc. 179 (2006), no. 843, vi+100 pp.Google Scholar
Osin, D.. Peripheral fillings of relatively hyperbolic groups. Invent. Math. 167 (2007), no. 2, 295–326.CrossRefGoogle Scholar
Redfern, I. D.. Automatic Coset Systems, PhD Thesis, University of Warwick, 1993.Google Scholar
Saito, K.. The limit element in the configuration algebra for a discrete group: a précis. Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990), 931–942, Math. Soc. Japan, Tokyo, 1991.Google Scholar