Notes of Mikael de la Salle’s Cambridge lecture 08-05-2017

Characterizing a vertex-transitive graph by a large ball

Joint with Romain Tessera.

Which Cayley graphs can be approximated with other graphs? We deal with simple, connected unoriented, locally finite graphs.

Say graphs {X} and {Y} are {R}-close, with {X} transitive, if every {R}-ball of {Y} is isomorphic to the {R}-ball in {Y}.


  • If normal subgroups {N_j} have {\bigcap N_j=\{1\}}, then {Cay(\Gamma/N_j,S)} converge to {Cay(\Gamma,S)}.
  • If {\Gamma=\langle S|R\rangle} is not finitely presented, set {R_j=R\cap B_S(R)}. Then {Cay(\langle S|R_j>,S)} converge to {Cay(\Gamma,S)}.
  • Beware that two non-isomorphic groups can have isomorphic Cayley graphs.

Two differences with soficity:

  • no labels,
  • no {\epsilon}, i.e. balls should coincide exactly.

Definition 1 A transitive graph is local to global rigid if there exists {R} such that for all graphs {Y}, {R}-close to {X}, {Y} is covered by {X}.


  • Regular trees are ltgr (with {R=1}).
  • (Benjamini-Ellis). The {{\mathbb Z}^d}-grid is ltgr (with {R=3}). Less obvious.
  • (Georgakopoulos). Planar 1-ended transitive graphs are ltgr.
  • Every Cayley graph of a torsion free groups of polynomial growth, lattices in simple real connected Lie groups are ltgr.
  • Quasi-trees are ltgr.
  • Bruhat-Tits buildings of {PGl(d,F)}, in characteristic 0, are ltgr.
  • Every finitely presented group (with at least one element of infinite order) admits a ltgr Cayley graph.


  • {Sl(4,{\mathbb Z})} amits a non ltgr Cayley graph.
  • {F_2\times F_2\times{\mathbb Z}/2{\mathbb Z}} is not ltgr, even among transitive graphs.
  • (Caprace). There exists a torsion-free lattice in {PGl(d,F_p((t)))} which is not ltgr.

1. Structure results

Most examples above follow from the following Theorem.

Theorem 2 If {X} is large scale simply connected and {Aut(X)} is countable, then {X} is ltgr.

Indeed, planar graphs, Cayley graphs of torsion free groups of polynomial growth (Trofimov), Cayley graphs of higher rank lattices (Furman) have countable automorphism groups.

Question. What about general groups of polynomial growth ?

1.1. Proof

By assumption, vertex stabilizers are finite. It follows that isometries are uniquely determined by their restriction to some ball. Therefore local isometries have unique extensions. Simple connectedness allows developing maps to be constructed.

2. Counterexamples

Let {H} be a group generated by finite subset {T}. Assume that {H^2(H,{\mathbb Z}/2{\mathbb Z})} is infinite, i.e. {H} has uncountably many different 2-fold coverings. The kernel of the obvious homomorphism {F_2\times F_2 \rightarrow {\mathbb Z}} does the job. Observe that both {G=Sl(4,{\mathbb Z})} and {G=F_2\times F_2\times {\mathbb Z}/2{\mathbb Z}} contain {H\times {\mathbb Z}/2{\mathbb Z}}.

By assumption, one can approximate the obvious graph {H\times {\mathbb Z}/2{\mathbb Z}} in uncountably many different ways. Pick generating system {S} of {G} such that {G\cap H=T}. A careful choice of {S} allows to recongnize just from the local combinatorics the {H} edges from the other ones, and thus to show invariance of the 2-fold covering map.

The main ingredient is a variant of the following fact: every group with an element of finite order has a Cayley graph with countable isometry group.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s