Simulations and the Lamplighter group
Abstract
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 we prove that the tiling problem (a.k.a. the “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 addressed 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.
Related
- Spectral computations on lamplighter groups and Diestel-Leader graphs
- Analytic, geometric and measured aspects of lamplighter-like groups
- Uncertainty in AI driven Monte Carlo simulations
- Uniqueness and structure-preserving numerical simulations for an Ultrahyperbolic Schrödinger equation
- Teleported free energy simulations
BibTeX
@article{bartholdi2026simulations,
title = {{Simulations and the Lamplighter group}},
author = {Laurent Bartholdi and Ville Salo},
journal = {Groups, Geometry, and Dynamics},
year = {2026},
month = nov,
doi = {10.4171/ggd/692},
url = {https://hal.science/hal-05849728v1},
note = {CC BY},
}
RIS
TY - JOUR
TI - Simulations and the Lamplighter group
AU - Laurent Bartholdi
AU - Ville Salo
PY - 2026
DA - 2026/11/03
JO - Groups, Geometry, and Dynamics
DO - 10.4171/ggd/692
UR - https://hal.science/hal-05849728v1
AB - 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 we prove that the tiling problem (a.k.a. the “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 addressed 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.
SN - 1661-7207
SN - 1661-7215
ER -