Vertex transitive graph with "intermediate dimensional" growth rate

Question

Given a function $f : \mathbb{N} \to \mathbb{N}$, I'm interested in if we can find a graph $G$ such that if $g(n)$ is the number of vertices in $G$ within distance $n$ from a given vertex, we have $\lim_{n\to\infty} f(n)/g(n) = c$ for some constant c. I'm particularly interested in the case where $g(n) = n^r$ for $r>1$; when $r$ is a natural number, the natural Cayley graph from $\mathbb{Z}^r$ has this property, and I'm curious if there are natural graphs of "intermediate dimension" in this sense. (of course, without a condition like vertex transitivity, this problem is trivial. I'm also interested in loosening vertex transitivity to something like finitely many orbits under the action of the automorphism group, or even something looser, if necessary)

Answer 1

If you look to Cayley graphs (which is a very particular class of vertex-transitive graph), the question you're asking is know as growth of groups.

A lot of things are known:

• for all $r \in \mathbb{Z}$, the groups which have polynomial growth $\Theta(n^r)$ are the groups which are virtually nilpotent (nilpotency is, broadly speaking, a generalization of commutativity, and one can get the $r$, see https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_of_polynomial_growth). A detailed research article would be https://arxiv.org/pdf/1908.06044.pdf. Notice that if a graph is of polynomial growth (meaning growth function $f_G(n)$ smaller that some polynomial), then there exists an integer $d$ and two constant $c_1,c_2 >0$ such that $c_1n^d \leq f_G(n) \leq c_2n^d$ (see V.I. TROFIMOV, Graphs with polynomial growth theorem 21 and Can transitive graphs have non-integer growth dimension?)

• there are groups with exponential growth $\Theta(a^n)$ for some $a>0$, you can think of the free group $\mathbb{F}_2$ (whose Cayley graph for the usual generating set is a $4$-regular tree, so growth function is $4.3^{n-1}$ for $n\geq 1$). Growth cannot be greater than exponential is the degree of your graph is bounded.

• there are groups with intermediate growth, which is greater than polynomial yet smaller than an exponential. The most famous one is Grigorchuk group, which has growth $exp({n^{.767...}})$, but it has been proven that many behaviour are possible (e.g. https://arxiv.org/pdf/1110.3650.pdf, see also https://arxiv.org/pdf/math/0607384.pdf). An open question, known as the gap conjecture, ask whether it is possible for a group to have growth smaller than $\exp(\sqrt{n})$ and still not be of polynomial growth (actually, no group of intermediate growth smaller than the Grigorchuk group is known yet). I don't know if thing are very different for vertex-transitive graph.