We introduce a notion of "simulation" for labelled graphs, in which edges of the simulated graph are realized by regular expressions in the simulating graph, and prove that the tiling problem (aka "domino problem") for the simulating graph is at least as difficult as that for the simulated graph. We apply this to the Cayley graph of the "lamplighter group" $L=\mathbb Z/2\wr\mathbb Z$, and more generally to "Diestel-Leader graphs". We prove that these graphs simulate the plane, and thus deduce that the seeded tiling problem is unsolvable on the group $L$. We note that $L$ does not contain any plane in its Cayley graph, so our undecidability criterion by simulation covers cases not covered by Jeandel's criterion based on translation-like action of a product of finitely generated infinite groups. Our approach to tiling problems is strongly based on categorical constructions in graph theory.
翻译:我们引入了标签图形的“模拟”概念, 模拟图的边缘通过模拟图中的常规表达式实现, 并证明模拟图的平面问题( 包括“ 多米诺问题 ” ) 至少与模拟图的平面问题一样困难。 我们把这个概念应用到“ 光滑体组” $L ⁇ mathbb Z/2\wr\mathbb Z$的 Cayley 图形中, 更一般地说到“ Diestel- Leader 图形 ” 。 我们证明这些图形模拟了平面, 从而推断出种子的平面问题在组里是无法解决的 $L$ 。 我们注意到, $L$ 并不包含 Cayley 图形中的任何平面, 因此我们通过模拟无法降解的标准覆盖了Jeandel 标准所没有覆盖的基于有限生成的无穷组产品的翻译- 像动作的案例。 我们的平面问题方法主要基于图形理论中的绝对构造 。