A1 Refereed original research article in a scientific journal

Simulations and the lamplighter group




AuthorsBartholdi Laurent, Salo Ville

PublisherEMS Press

Publication year2022

JournalGroups, Geometry, and Dynamics

Journal name in sourceGROUPS GEOMETRY AND DYNAMICS

Journal acronymGROUP GEOM DYNAM

Volume16

Issue4

First page 1461

Last page1514

Number of pages54

ISSN1661-7207

eISSN1661-7215

DOIhttps://doi.org/10.4171/GGD/692(external)

Web address https://ems.press/journals/ggd/articles/8202027(external)

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/178966923(external)


Abstract
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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 19:48