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$?

  • $\begingroup$ Is this group theory, or graph theory? $\endgroup$ – Gerry Myerson Apr 4 '17 at 13:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Noah Stein Apr 4 '17 at 14:01
  • 1
    $\begingroup$ Actually, vertex transitive graphs are closely connected to group theory. $\endgroup$ – Jan-Christoph Schlage-Puchta Apr 4 '17 at 14:43
  • $\begingroup$ I edited accordingly. $\endgroup$ – YCor Apr 4 '17 at 17:18
  • $\begingroup$ 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$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.