The growth rate of a group $B_n(G, T)$ is based on the number of vertices that can be reached from a given one by $n$ steps along an edge in the Cayley graph of the group, where $G$ is the group (or its graph) and $T$ is a set of generators of the group or the respective edges in the graph.

I learned here that $\mathbb{Z}^3$ has a growth rate of the order of $n^3$. Looking at graphs (not necessarily Cayley), I wonder if the following exists for an arbitrary but fixed $n_0\in\mathbb{N}$:

  1. The graph is infinite.
  2. The graph is symmetric.
  3. The growth rate is of order $n^3$.
  4. Each vertex has $m>=n_0$ edges.

This exists for $m=n_0=6$ per the tiling of three dimensional space with cubes.

Question: Is the following proof that I can find an $m$ for any $n_0$ correct? (Risking a yes/no question as per this meta post.)

Define a graph $G_1 = (V, E_1)$ such that $V=\mathbb{Z}^3$. The vertices can be considered centers of cubes that tile $\mathbb{R}^3$. Define an edge of the graph for each two cubes that "touch" directly, either on sides, edges or corners. Consider a Rubik's Cube, where center cube has an edge to all surrounding cubes. More formally, let $v, w\in V$ be connected, i.e. $\{v, w\}\in E_1$, if they are "direct neighbors" along any coordinate combination, i.e. $v-w \in \{-1,0,1\}^3$ and $v\neq w$.

The ball $B_n(G_1, v)\subset V$ shall be the set of nodes reachable from $v$ with a minimal path length of $\leq n$. For $n=1$ this is again like looking at Rubik's Cube and $|B_1(G_1, v)| = 3^3 = 27$. In general the number of elements in the ball $B_n$ is an ever bigger "Rubik's Cubes" albeit always with an odd number of cubes along one dimension: $$|B_n(G_1, v)| = (1+2n)^3$$ So the growth rate is of the order of $n^3$, but we don't yet have an arbitrary large number of neighbors for a given vertex.

Now we define the graph $G_k=(V,E_k)$ based on $G_1$ such that we add edges to $E_1$ from $v$ to every vertex $w\in B_k(G_1, v)\setminus E_1$, so that now all vertices of that ball are direct neighbors of $v$.

In the new graph, we have $$ |B_n(G_k, v)| = (1+kn)^3$$ which still is a growth rate of order $n^3$, but since we are free to choose $k$, we can create a symmetric graph of order $n^3$ were each vertex has arbitrary many edges going out.

Specific head-scratchers

  1. Is $|B_n(G_k, v)|$ correct?
  2. Is the constructed graph $G_k$ really symmetric?

1 Answer 1


Yes, this is a fine construction. (Or: no, the group growth rate doesn't limit the degree of vertices.) A generalization of this: if you find an infinite graph $G$ which is symmetric, connected, and has a growth rate $|B_n(G,v)| = O(f(n))$, then we can let $G^k$ be the graph with an edge $vw$ whenever $d(v,w) \le k$ in $G$. We can make $G^k$ have arbitrarily large minimum degree, and still have$ |B_n(G^k,v)| = O(f(n))$.

We can even find a Cayley graph that will have the property you want. Take the group $\mathbb Z^3 \times \mathbb Z_2^k$, and take $T$ to be a set of $3+k$ generators corresponding to each of the factors. Then each vertex of the Cayley graph will have degree $6+2k$, and the growth rate will be $O(n^3)$. (The idea is that after $n$ steps, there are $O(n^3)$ possibilities for the element of $\mathbb Z^3$ we have, and at most $2^k = O(1)$ possibilities for the element of $\mathbb Z_2^k$.)

Or, we could even take $\mathbb Z^3$, but with a different, larger generating set. The growth rate will still be $O(n^3)$, because if no generator lets you change any coordinate by more than $M$, then after $n$ steps we are limited to a cube with $(2Mn+1)^3$ vertices in it. The degree of each vertex is twice the number of generators.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .