THE DOMINO PROBLEM FOR HYPERBOLIC GROUPS

THE DOMINO PROBLEM FOR HYPERBOLIC GROUPS

May 10th, 2023 | LAURENT BARTHOLDI
The domino problem for hyperbolic groups asks whether there exists an algorithm to determine if a Cayley graph of a group can be edge-covered by dominoes such that colors match at vertices. Laurent Bartholdi proves that for every non-virtually free hyperbolic group, no such algorithm exists, answering a conjecture by Aubrun, Barbieri, and Moutot and advancing a long-standing conjecture by Ballier and Stein. The domino problem is decidable for groups with a finite-index free subgroup, but undecidable for others. For example, it is undecidable on Z² and groups containing Z² as a subgroup. It is also undecidable for groups admitting a translation-like action of Z², including hyperbolic groups. The paper introduces a general criterion for undecidability of the domino problem on a graph, based on simulating a sequence of connected, infinite amenable graphs with contractions. This criterion subsumes known results and applies to hyperbolic groups. The paper shows that the domino problem is undecidable for word hyperbolic groups that are not virtually free. It uses a construction involving horospheres and a subshift of finite type to simulate a 2-regular tower of graphs, proving that such groups have undecidable domino problems. The key idea is that hyperbolic groups can simulate the geometry of the hyperbolic plane, leading to undecidability. The paper also discusses the implications of hyperbolicity, such as rational growth series and regular languages, and connects the domino problem to subshifts of finite type and Boolean algebras. The results highlight the complexity of the domino problem in hyperbolic groups and its connection to broader questions in geometric group theory.The domino problem for hyperbolic groups asks whether there exists an algorithm to determine if a Cayley graph of a group can be edge-covered by dominoes such that colors match at vertices. Laurent Bartholdi proves that for every non-virtually free hyperbolic group, no such algorithm exists, answering a conjecture by Aubrun, Barbieri, and Moutot and advancing a long-standing conjecture by Ballier and Stein. The domino problem is decidable for groups with a finite-index free subgroup, but undecidable for others. For example, it is undecidable on Z² and groups containing Z² as a subgroup. It is also undecidable for groups admitting a translation-like action of Z², including hyperbolic groups. The paper introduces a general criterion for undecidability of the domino problem on a graph, based on simulating a sequence of connected, infinite amenable graphs with contractions. This criterion subsumes known results and applies to hyperbolic groups. The paper shows that the domino problem is undecidable for word hyperbolic groups that are not virtually free. It uses a construction involving horospheres and a subshift of finite type to simulate a 2-regular tower of graphs, proving that such groups have undecidable domino problems. The key idea is that hyperbolic groups can simulate the geometry of the hyperbolic plane, leading to undecidability. The paper also discusses the implications of hyperbolicity, such as rational growth series and regular languages, and connects the domino problem to subshifts of finite type and Boolean algebras. The results highlight the complexity of the domino problem in hyperbolic groups and its connection to broader questions in geometric group theory.
Reach us at info@study.space
Understanding The domino problem for hyperbolic groups