Growth Rates in Infinite Graphs and Permutation Groups
Dugald Macpherson · Proceedings of the London Mathematical Society · 1985
If Γ is an infinite graph, let mk(Γ) be, for each k ∈ N, the number of isomorphism types of k-vertex subgraphs. If G is a permutation group on an infinite set X, let nk(G) be the number of orbits of G on k-subsets of X. It is shown that if mk(Γ) or nk(G) is not bounded above polynomially, then asymptotically it is bounded below by any function of the form exp(k½ − ɛ) where ε > 0 and ε ∈ R;. The proof uses the techniques of [8].