Counting subgraphs in fftp graphs with symmetry

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.

version 2, 27 pages, 3 figures, exposition improved after the comments of the referee