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

Abstract

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 $3$ around each vertex is isomorphic to the ball of radius $3$ in ${\mathbb{L}}^d$, for each integer $d\ge 3$. These graphs have a very rigidly proscribed global structure, much more so than that of $(2d)$-regular graphs. (They may be viewed as quotient lattices of ${\mathbb{L}}^d$ in various compact orbifolds.) In the $d=2$ case, our methods yield new proofs of structure theorems of Thomassen and of Márquez, de Mier, Noy and Revuelta, and also yield short, `algebraic' restatements of these theorems. Our proofs use a mixture of techniques and results from combinatorics, algebraic topology and group theory.

23 pages, shortened proofs, one new figure

Cited by in corpus (2)

• Bounds on curvature in regular graphs
• Local-to-Global-rigidity of lattices in $S{L}_n(\mathbb{K})$