Counting subgraphs in hyperbolic graphs with symmetry. (English) Zbl 1323.05064

Summary: We confirm a conjecture of K. Saito [Publ. Res. Inst. Math. Sci. 46, No. 1, 37–113 (2010; Publ. Res. Inst. Math. Sci. 46, No. 1, 37–113 (2010; Zbl 1208.05057)] on the growth functions of graphs, which was originally posed for hyperbolic groups.


05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05A15 Exact enumeration problems, generating functions
05C30 Enumeration in graph theory
20F67 Hyperbolic groups and nonpositively curved groups
37D40 Dynamical systems of geometric origin and hyperbolicity (geodesic and horocycle flows, etc.)


Zbl 1208.05057
Full Text: DOI arXiv Euclid


[1] L. Bartholdi, M. Neuhauser and W. Woess, Horocyclic products of trees, Jour. Eur. Math. Soc., 10 (2008), 771-816. · Zbl 1155.05009
[2] D. Calegari, The ergodic theory of hyperbolic groups, Contemp. Math., 597 (2013), 15-52. · Zbl 1283.20052
[3] D. Calegari and K. Fujiwara, Combable functions, quasimorphisms, and the central limit theorem, Ergodic Theory Dynam. Systems, 30 (2010), 1343-1369. · Zbl 1217.37025
[4] J. W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata, 16 (1984), 123-148. · Zbl 0606.57003
[5] M. Coornaert, Mesures de Patterson-Sullivan sur le bord d’un espace hyperbolique au sens de Gromov, Pacific J. Math., 159 (1993), 241-270. · Zbl 0797.20029
[6] R. Diestel and I. Leader, A conjecture concerning a limit of non-Cayley graphs, J. Algebraic Combin., 14 (2001), 17-25. · Zbl 0985.05020
[7] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson and W. P. Thurston, Word Processing in Groups, Boston, MA, Jones and Bartlett Publishers, 1992. · Zbl 0764.20017
[8] D. B. A. Epstein, A. R. Iano-Fletcher and U. Zwick, Growth functions and automatic groups, Experiment. Math., 5 (1996), 297-315. · Zbl 0892.20022
[9] A. Eskin, D. Fisher and K. Whyte, Coarse differentiation of quasi-isometries I, Spaces not quasi-isometric to Cayley graphs, Ann. Math. (2), 176 (2012), 221-260. · Zbl 1264.22005
[10] P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. · Zbl 1165.05001
[11] V. Kaimanovich and W. Woess, Boundary and entropy of space homogeneous Markov chains, Ann. Prob., 30 (2002), 323-363. · Zbl 1021.60056
[12] M. Pfeiffer, Automata and Growth Functions for the Triangle Groups, Diploma Thesis in Computer Science, Rheinisch-Westfälische Technische Hochschule Aachen, March, 2008.
[13] K. Saito, Limit elements in the configuration algebra for a cancellative monoid, Publ. Res. Inst. Math. Sci., 46 (2010), 37-113. · Zbl 1208.05057
[14] K. Saito, Opposite power series, European J. Combin., 33 (2012), 1653-1671. · Zbl 1267.30006
[15] K. Saito, Private communication. · Zbl 0759.05076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.