ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE
For each integer $d\geqslant 3$ , we obtain a characterization of all graphs in which the ball of radius $3$...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2016-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S205050941600030X/type/journal_article |
| Summary: | For each integer
$d\geqslant 3$
, we obtain a characterization of all graphs in which the ball of radius
$3$
around each vertex is isomorphic to the ball of radius 3 in
$\mathbb{L}^{d}$
, the graph of the
$d$
-dimensional integer lattice. The finite, connected graphs with this property have a highly rigid, ‘global’ algebraic structure; they can be viewed as quotient lattices of
$\mathbb{L}^{d}$
in various compact
$d$
-dimensional orbifolds which arise from crystallographic groups. We give examples showing that ‘radius 3’ cannot be replaced by ‘radius 2’, and that ‘orbifold’ cannot be replaced by ‘manifold’. In the
$d=2$
case, our methods yield new proofs of structure theorems of Thomassen [‘Tilings of the Torus and Klein bottle and vertex-transitive graphs on a fixed surface’, Trans. Amer. Math. Soc.
323 (1991), 605–635] and of Márquez et al. [‘Locally grid graphs: classification and Tutte uniqueness’, Discrete Math.
266 (2003), 327–352], and also yield short, ‘algebraic’ restatements of these theorems. Our proofs use a mixture of techniques and results from combinatorics, geometry and group theory. |
|---|---|
| ISSN: | 2050-5094 |