The domino problem for hyperbolic groups

By Laurent Bartholdi. 2023

986 citations recorded by the source corpus.

We prove, for every non-virtually free hyperbolic group $G$, that there is no algorithm that, given a finite collection of dominoes, determines whether the Cayley graph of $G$ may be edge-covered by these dominoes so that colours match at vertices. This answers a conjecture by Aubrun, Barbieri and Moutot and goes towards settling a long-standing conjecture of Ballier and Stein.

View Paper: https://www.semanticscholar.org/paper/0bb033ef1e3113f3dd7a01666bcc4ac3b5794c1b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Some problems on mapping class groups and moduli space (2006, background): “Is it true that, given any pseudo-Anosov φ ∈ Modg, there exists n = n(φ) such that the normal closure of φn is free? Gromov discovered the analogous phenomenon for elements of hyperbolic type inside nonelementary word-hyperbolic groups; see [Gro], Theorem 5.”
Ripser: efficient computation of Vietoris–Rips persistence barcodes (2019, unknown): “Vietoris–Rips complex were first introduced by Vietoris [50] as a means of defining a homology theory for general compact metric spaces, and later used by Rips in the study of hyperbolic groups (see [18]).”
Fundamental Groups of Blow-ups (2002, background): “Results of Gromov [G] and Moussong [M] show that the condition that a Coxeter cell complex be nonpositively curved in the sense of Aleksandrov and Gromov is equivalent to a condition on the link of each vertex.”
Chordality and hyperbolicity of a graph (2009, background): “By a simple but nice argument, Gromov shows that G is 2δ-hyperbolic provided it is δ-hyperbolic with respect to any given vertex [2, Proposition 2.2] [61, 1.1B].”
Equivariant covers for hyperbolic groups (2006, background): “1 j‚Œ˛n;ˇn .tn/ ‚Œ˛;ˇ .tn/j D 0: Since yD and the Gromov product are continuous, we get using (8.6) and (8.7) lim n!”
Finiteness properties of cubulated groups (2012, methodology): “The following is Gromov’s definition of relative hyperbolicity from [Gro87], as elaborated by Bowditch in [Bow12].”
On metric relative hyperbolicity (2012, background): “The notion of (strong) relatively hyperbolicity first appeared in [Gro87], see also [Bow99, Far98], and has been studied only in the context of groups until Druţu and Sapir [DS05a] gave a metric characterization and discovered several properties of the geometry of Cayley graphs of relatively hyperbo”
A combination theorem for strong relative hyperbolicity (2006, background): “In this section, we shall first recall certain notions of relative hyperbolicity due to Farb [10] and Gromov [14].”
The boundary at infinity of the curve complex and the relative Teichmüller space (2018, background): “References for the material in this section are [8], [9], [5] and [4].”
A random tunnel number one 3–manifold does not fiber over the circle (2005, methodology): “An example theorem is that a 2–generator 1–relator group is word-hyperbolic with probability 1 (Gromov [12], Ol’shanskii [25]).”
Lacunary hyperbolic groups (2007, methodology): “brief, the idea of the proof is to translate Gromov’s local-to-global result in [20], which is expressed using isoperimetric information, into one using ı–hyperbolicity.”
Lipschitz equivalence of self-similar sets and hyperbolic boundaries (2012, background): “The notion of hyperbolic graph was introduced by Gromov [7,21].”
Residual finiteness, QCERF, and fillings of hyperbolic groups (2008, background): “Relative hyperbolicity was first defined by Gromov in [7].”
Normal automorphisms of relatively hyperbolic groups (2008, methodology): “In this paper we use the notion of relative hyperbolicity, which is sometimes called strong relative hyperbolicity and goes back to Gromov [16].”
Hereditary conjugacy separability of right angled Artin groups and its applications (2009, background): “Since H has finite index in G, it is also word hyperbolic ([27]), thus, according to Lemma 9.”