Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-44626
Titel: Simulations and the lamplighter group
VerfasserIn: Bartholdi, Laurent
Salo, Ville
Sprache: Englisch
Titel: Groups, geometry, and dynamics : GGD
Bandnummer: 16
Heft: 4
Seiten: 1461-1514
Verlag/Plattform: EMS Publ.
Erscheinungsjahr: 2022
DDC-Sachgruppe: 510 Mathematik
Dokumenttyp: Journalartikel / Zeitschriftenartikel
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=Z/2≀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.
DOI der Erstveröffentlichung: 10.4171/ggd/692
URL der Erstveröffentlichung: https://ems.press/journals/ggd/articles/8202027
Link zu diesem Datensatz: urn:nbn:de:bsz:291--ds-446269
hdl:20.500.11880/39795
http://dx.doi.org/10.22028/D291-44626
ISSN: 1661-7215
1661-7207
Datum des Eintrags: 13-Mär-2025
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Mathematik
Professur: MI - Prof. Dr. Laurent Bartholdi
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
10.4171-ggd-692.pdf739,67 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons