# Finite vertex-transitive graphs that look like infinite vertex-transitive graphs

For a vertex-transitive graph $G$ and a positive integer $d$, and let $G(d)$ be the subgraph induced by all vertices of $G$ within distance $d$ of some given vertex $v$ (since $G$ is vertex-transitive, this doesn't depend on $v$).

Given an infinite (but locally-finite) graph $G$, does there always exist a finite vertex-transitive graph $G_d$ such that $G(d)$ is isomorphic to $G_d(d)$ (intuitively, a neighborhood of radius $d$ in the infinite graph "looks like" a neighborhood of radius $d$ in the finite graph)? If so, are there any good methods for constructing such a graph (given some nice representation of $G$, say as a Cayley graph of some infinite group). It seems that if $G$ is the Cayley graph of some group (which is true by Sabidussi's theorem), then it might be possible to take some presentation of this group and add some extra relations so it becomes finite, but I haven't been able to make this method work.

One example of a graph $G$ where such a family of graphs $G_d$ exists are lattice graphs $\mathbb{Z}^m$ (where points are connected if they are at unit distance); these are similar to toroidal grid graphs $(\mathbb{Z}/d\mathbb{Z})^m$. I can also construct other such graphs $G$ by "adding edges" to $\mathbb{Z}^m$ (by say, connecting all points at distance < 5). Barring a positive answer to the above question, are there any other graphs $G$ where such a family exists?

• The is an old paper by Pavol Hell "Graphs with given neighbourhoods". This is not focussed on vertex-transitive graphs (iirc), but I think there is a good chance that some of the methods carry over. – Chris Godsil Mar 29 '13 at 13:54
• By the way, do you know if there exists somewhere a database associating a graph G to a graph H "such that any neighborhood is a copy of G" ? I wonder both if it exists and if starting one in Sage would be useful :-) – Nathann Cohen Mar 29 '13 at 14:25
• @Nathann Cohen: I am not aware of any such database, nor do I know of any potential application for one. – Chris Godsil Mar 30 '13 at 21:20

A group $G$ is called residually finite if, for every non-trivial $g$, there exists a finite quotient $f:G\to Q$ such that $f(g)\neq 1$.

It's an easy argument that a finitely generated group $G$ is residually finite if and only if, for every $n$, there exists a finite quotient $f:G\to Q$ such that $f$ restricts to an injection on the ball of radius $n$ in the Cayley graph of $G$

In particular, the Cayley graph of any finitely generated group has your property if the group is residually finite (thanks to Boris Bukh for his comments below).

Many groups are residually finite---for instance, Mal'cev proved that all finitely generated linear groups have this property (brief proof---reduce modulo a suitable maximal ideal).

However, there are non-residually finite groups. One of the simplest examples is the (2,3)-Baumslag--Solitar group with presentation

$BS(2,3)=\langle a,b\mid b^{-1}a^2b=a^3\rangle$ .

Of course, there are much more sophisticated examples---Higman constructed an infinite, finitely generated group with no non-trivial finite quotients, and there are even infinite, finitely generated, simple groups.

• For the original question, isn't it conceivable that an infinite graph has symmetry group $G$, but for every $d$ there is a group $G_d$ and a set of generators such that the Cayley graph looks like $G$ in a neighborhood of size $d$, but these groups $G_d$ have nothing whatsoever to do with the original $G$? – Boris Bukh Mar 29 '13 at 20:49
• Not when $G$ is finitely presentable. If the ball $B_n$ is large enough that it contains loops corresponding to all relations of $G$, then any finite group with $B_n$ embedded in its Cayley graph is necessarily a quotient, since it satisfies all the relations of $G$. When $G$ is finitely generated but not finitely presentable, yes, it's conceivable. – HJRW Mar 29 '13 at 20:59
• I am sorry, but I remain unconvinced. We see the loops, but how do we write from knowing the loops the relations? The edges are not labelled with the names of generators. So, we do not know that two "parallel-looking" edges correspond to the same generator. – Boris Bukh Mar 29 '13 at 21:28
• Sorry, Boris, of course you're right. I was implicitly assuming that the approximating graphs are Cayley graphs. – HJRW Mar 30 '13 at 6:30
• Oh - are you claiming that Schreier graphs are transitive? They are not! – R W Mar 30 '13 at 20:17