The domino problem on groups and Schreier graphs

Consider a directed graph with edge labels in a finite set $S$. The \emph{domino problem} asks, given a finite set of ``dots'' $A$ and a set of ``dominos'' $\Theta\subset A\times S\times A$, whether dots can be assigned to the graph's vertices in such a manner that every edge carries an allowed domino, namely $(\text{dots at begin},\text{edge label},\text{dots at end})\in\Theta$ for every edge.

This problem is a small fragment of the monadic second order logic of the graph, and we are interested in knowing when it is decidable. In particular, the graph could be the Cayley graph of a group $G$ with generating set $S$, and then a conjecture of Baller and Stein asserts that the domino problem is decidable if and only if $G$ is virtually free. I will describe recent results (partly joint with Ville Salo) proving partial cases of this conjecture, in particular for metabelian groups, and for word hyperbolic groups.

I will also consider Schreier graphs of $G$-sets for some self-similar groups $G$, and give examples close to the border between decidability and undecidability of the domino problem.