Domino problems on graphs and groups

Abstract: For a fixed edge-labelled graph, the "domino problem" asks: "given a collection of labelled dominoes (with numbers on their ends), can one put a domino on each edge of the graph in such a manner that edge labels and vertex numbers match?''

In spite of its naive appearence, this problem is deeply connected to (monadic, second-order) logic; remarkably, it is undecidable for graphs such as the infinite square grid – the "Wang tiling problem".

I will consider it on graphs produced from a group action: Cayley graphs, Schreier graphs. I will exhibit a class of graphs for which the problem is decidable, as well as interesting examples not containing grids yet also having undecidable domino problem.

Part of this is joint work with Ville Salo.

algebraic topologydifferential geometrygeneral topologygroup theorygeometric topology

Audience: researchers in the topic

Ohio State Topology and Geometric Group Theory Seminar

Series comments: https://sites.google.com/view/topoandggt