ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE
ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE
复制标题
关于局部与格不可区分的图的结构
DOI：
10.1017/fms.2016.30
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
David Ellis
中科院分区：
文献类型：
--
作者：
I. Benjamini;David Ellis
对于每个整数$d\geqslant 3$，我们得到了每个顶点周围半径为$3$的球与$\mathbb{L}^{d}$中半径为3的球同构的图的一个特征.具有这一性质的有限连通图具有高度刚性的“整体”代数结构；它们可以看作是由结晶学群产生的各种紧凑的$d维二叉形中的商格构成的。我们给出的例子表明，“半径3”不能用“半径2”代替，“奥比福尔德”也不能用“流形”代替。在$d=2$的情形下，我们的方法给出了Thomassen[‘Tilings of the Torus and Klein Bottle and Vertex-Transfer Groups on a First Surface’，Trans.阿默。数学课。SoC。323(1991)，605-635]和马尔克斯等人。[‘局部网格图：分类和图特唯一性’，离散数学。266(2003)，327-352]，也给出了这些定理的简短的“代数”重述。我们的证明混合使用了组合学、几何学和群论的技术和结果。
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.