A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Simulations and the lamplighter group
Tekijät: Bartholdi Laurent, Salo Ville
Kustantaja: EMS Press
Julkaisuvuosi: 2022
Journal: Groups, Geometry, and Dynamics
Tietokannassa oleva lehden nimi: GROUPS GEOMETRY AND DYNAMICS
Lehden akronyymi: GROUP GEOM DYNAM
Vuosikerta: 16
Numero: 4
Aloitussivu: 1461
Lopetussivu: 1514
Sivujen määrä: 54
ISSN: 1661-7207
eISSN: 1661-7215
DOI: https://doi.org/10.4171/GGD/692
Verkko-osoite: https://ems.press/journals/ggd/articles/8202027
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/178966923
We introduce a notion of "simulation" for labelled graphs, in which edges of the simu-lated 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 = Z=2 Z 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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
