# Finite and infinite 4-regular vertex-transitive graphs with identical $R$-balls

Consider the set of all 4-regular connected vertex-transitive graphs.

By compactness, for every integer $R \ge 0$, there is an integer $N_R$, so that for every 4-regular vertex-transitive graph of radius larger than $N_R$, there is an infinite vertex-transitive graph with identical $R$-balls.

Do we know any bounds on $N_R$?

• Is this group theory, or graph theory? – Gerry Myerson Apr 4 '17 at 13:02
• If you choose a more informative title and tags, you will increase the chance that someone who can answer will see the question and respond. – Noah Stein Apr 4 '17 at 14:01
• Actually, vertex transitive graphs are closely connected to group theory. – Jan-Christoph Schlage-Puchta Apr 4 '17 at 14:43
• I edited accordingly. – YCor Apr 4 '17 at 17:18
• Obviously equivalent, but maybe useful for intuition: $N_R$ is the largest radius of a 4-regular vertex-transitive graph whose $R$-ball are not isomorphic to the $R$-ball in any infinite vertex-transitive graph. I have no idea even to prove that $N_R\gg R$. – YCor Apr 4 '17 at 18:22

This is not an answer to the question, but it is a bit long for a comment.

My aim here is to note that, if one works with Cayley graphs with edges oriented and labeled by the corresponding generators $S=\{a,b\}$, then it is known that the analogous number $N'_R$ grows at least exponentially fast with respect to $R$. (One can replace $4$ by some fixed integer in "$4$-regular", or equivalently $S$ by some larger fixed finite set.)

The basic observation is the following: if $G$ is a group with finite generating set $S$, then its Cayley graph has the same labeled $R$-ball as some infinite Cayley graph if and only if the group $\langle S\mid A\rangle$ if infinite, where $A$ are the group words of length less than $2R$ that are trivial in $G$.

Indeed, $\langle S\mid A\rangle$ is the largest group with the same $R$-balls as $G$, because every relation in $G$ that one can see in a ball of radius $R$ has length $\leq 2R$.

This observation leads to the following equivalent definition of $N'_R$. Consider all presentations $\langle S\mid A\rangle$ for $A$ a set of group words of length less than $2R$ with respect to $S$. We get finitely many group presentations, some of infinite groups and some of finite groups. Then $N'_R$ is the maximal radius of those finite groups.

It is known that there are finite groups with relations of length $\leq R$ and radius $\geq e^{cR}$. For example the finite nonabelian simple groups, see the paper Presentations of finite simple groups: a quantitative approach (or arXiv link) by Guralnik, Kantor, Kassabov and Lubotzky. One concludes that $N'_R \geq e^{cR}$ for labeled Cayley graphs.

For unlabeled Cayley graphs, I wonder whether the finite simple groups can be used to show that $N_R$ also grows at least exponentially. My gut feeling is that $N_R$ grows much faster.