Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
1  
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
3  
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
1  
Oh - are you claiming that Schreier graphs are transitive? They are not! –  R W Mar 30 '13 at 20:17
show 4 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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