We conjecture that a finitely generated group has a decidable domino problem if and only if it is virtually free. We show this is true for all virtually nilpotent finitely generated groups (or, equivalently, groups of polynomial growth), and for all finitely generated groups whose center has a non-trivial, finitely generated and torsion-free subgroup.
Our proof uses a reduction of the undecidability of the domino problem on any such group to the undecidability of the domino problem on , under the assumption that is not virtually free. This is achieved by first finding a thick end in , and then relating the thick end to the existence of a certain structure, resembling a half-grid, by an extension of a result of Halin.
Cite this article
Alexis Ballier, Maya Stein, The domino problem on groups of polynomial growth. Groups Geom. Dyn. 12 (2018), no. 1, pp. 93–105DOI 10.4171/GGD/439