Are two quasi-isometric, isomorphic on large enough balls, transitive graphs isomorphic?

Question

Take two transitive graphs $X,Y$ (potentially directed and edge-labelled, e.g. Cayley graphs). Assume $X,Y$ are quasi-isometric with constant $K$, i.e. there exists a function $f:VX \to VY$ ($VX,\,VY$ are the respective vertex sets) such that:

• Any vertex of $Y$ is at most at distance $K$ from the image of a vertex of $f(X)$,
• For any $x,x' \in VX$, we have $$K^{-1}d(x,x')-K \leq d(fx,fx') \leq Kd(x,x') + K.$$ Furthermore, assume that the balls of $X$ and $Y$ of radius $ \leq 2K$ are isomorphic.

Question. Does it follow that $X$ and $Y$ themselves are isomorphic?

At first, my intuition would say "yes" because the graphs are "the same" both in their coarse structure, and locally, but after further thoughts, maybe the local and global similarities don't match.

It seems that this question is natural enough to have been studied before, but Google didn't help.

Note. The constant $2K$ has been chosen semi-arbitrarily: if it is taken to be too small, the question can be answered negatively, e.g. by considering two cycle graphs of different length.

Answer 1

Questions of this flavour have indeed been studied before. There may be earlier references, but I know at least a body of work that was initiated by Benjamini, Ellis and Georgakopoulos (see here for precise references). They were interested in a question that is not exactly yours, but rather whether, given a transitive graph $X$, there is a constant $R$ such that any other graph $Y$ that has the same balls of radius $R$ as $X$ is covered by $X$. Such a graph is called Local-Global rigid. Many graphs are LG-rigid, but not all.

In a paper with Romain Tessera, we tried to address some of these questions. And one of our constructions is as follows: for every integer $R$, we construct a continuum of pairwise non-isomorphic vertex-transitive graphs $(X_i)$ that have the same balls of radius $R$ and are all quasi-isometric to a product of two $4$-regular trees with constant $4$. You can replace "product of two $4$-regular trees" by other models, for example $\mathrm{SL}_4(\mathbf Z)$. See Theorem H in the above reference for a precise statement. This answers your question negatively.

The situation is probably quite different if you restrict to Cayley graphs (even regarded as unlabeled unoriented graphs). For example, if $X$ is the Cayley graph of a finitely presented group $G$, then there is a constant $R(K,X)$ such that any other Cayley graph that is $K$-QI to $X$ and has the same balls of radius $R(K,X)$ than $X$ is isomorphic to $X$. This is quite obvious: there are only finitely many Cayley graphs that are $K$-QI to $X$.

Added later a justification of the last assertion

The assertion is that, if $X$ is the Cayley graph of a finitely presented group, there are only finitely many Cayley graphs with given degree (this assumption what forgotten) which are $K$-QI to $X$. This follows from the following lemma, which bounds the length of the relators in a presentation of a group whose Cayley graph is $K$-QI to $X$.

Lemma: Let $(G,S)$ and $(H,T)$ be two groups with finite generating sets, such that the associated Cayley graphs $X$ and $Y$ are quasi-isometric with constant $K$. If $G$ has a presentation $G=\langle S \mid R\rangle$ with relators of length $\leq \ell$, then $H$ has a presentation $H=\langle T \mid R'\rangle$ with relators of length $\leq f(\ell,K)$ for some function $f$.

Proof: the fact that $G$ admits such a presentation with relators of length $\ell$ is equivalent to $X$ being simply connected at scale $\ell$ (meaning that filling all loops of length $\leq \ell$ in $X$ turns $X$ into a simply connected space). But being simply connected at large scale is QI-invariant, see for example Theorem 2.2 here. So $Y$ is simply connected at scale $f(\ell,K)$, and the lemma follows.