# Does the group growth rate limit the number of edges going out of a vertex in its Cayley graph?

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.

1. Is $$|B_n(G_k, v)|$$ correct?
2. Is the constructed graph $$G_k$$ really symmetric?
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.