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

Question

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?

Answer 1

For Cayley graphs, you're basically asking about residually finite groups.

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.

Answer 2

Several comments.

First, it is wrong to interpret the Sabidussi theorem as claiming that vertex transitive graphs are necessarily Cayley graphs. Sabidussi's theorem contains an additional condition of existence of a simply transitive action. Without this assumption the claim is false. Eskin, Fisher and Whyte recently proved that so-called Diestel-Leader graphs are not even quasi-isometric to any Cayley graph of a finitely generated group in spite of being vertex transitive.

Second. The group of isomorphisms of vertex transitive graphs which satisfy your approximation property must necessarily be unimodular, so that any vertex transitive graph whose group of isomorphisms is not unimodular provides a counterexample. Such graphs do exist; probably the simplest is the so-called "grandfather graph". The Diestel-Leader graphs used by Eskin et al. also have non-unimodular group of isomorphisms.

Third. As it was pointed out by HW, for edge-labelled Cayley graphs finitely presented groups which are not residually finite provide a counterexample (it is, indeed, less clear what happens for unlabelled Cayley graphs). Note also that your approximation is way stronger than the one required in the definion of sofic groups. In particular, existence of such approximation would imply that the considered group is sofic. Whether any finitely generated group is sofic is currently unknown, but most people believe that there is no reason for that.