MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
