On the structure of graphs which are locally indistinguishable from a lattice

Itai Benjamini, David Ellis

Published 2014-09-26Version 1

We study the properties of finite graphs in which the ball of radius $r$ around each vertex induces a graph isomorphic to some fixed graph $F$. This is a natural extension of the study of regular graphs, and of the study of graphs of constant link. We focus on the case where $F$ is $\mathbb{L}^d$, the $d$-dimensional square lattice. We obtain a characterisation of all the finite graphs in which the ball of radius $2$ around each vertex is isomorphic to the ball of radius $2$ in $\mathbb{L}^2$, and of all the finite graphs in which the ball of radius $3$ around each vertex is isomorphic to the ball of radius $3$ in $\mathbb{L}^d$, for each integer $d \geq 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory.