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 标准所没有覆盖的基于有限生成的无穷组产品的翻译- 像动作的案例。 我们的平面问题方法主要基于图形理论中的绝对构造 。

0
下载
关闭预览

相关内容

专知会员服务
80+阅读 · 2021年7月31日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
已删除
将门创投
3+阅读 · 2017年10月27日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年11月23日
Quantum Advantage for All
Arxiv
0+阅读 · 2021年11月23日
Arxiv
0+阅读 · 2021年11月23日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
已删除
将门创投
3+阅读 · 2017年10月27日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员