The Domino problem on rhombus-shaped tiles.
Time: 14:00 -- Location: LRI, 445
summary: The word tiling is a name for several models: geometrical tilings,
where you tile the plane with geometrical shapes like a jigsaw puzzle; and
symbolic tilings, where you tile the plane while matching colors on the edges
of tiles. You can use both kinds of constraints; a well-known example is the
Penrose tiling, which is studied for its quasiperiodic properties; recently
the purely geometrical Einstein tiling has made some noise.
The Domino problem - given a set of tiling rules, is it possible to tile the
plane? - is the classical undecidable problem in this domain; it is a kind of
one-player game. There has been many results that can be described as trying
to play this game in different structures (in groups, fractals, subshifts...)
to determine when the problem is decidable and undecidable to better understand
both the problem and the properties of the structures.
With Victor Lutfalla, we play this game on geometrical tilings that use rhombus-shaped
tiles and we show that the Domino problem is always undecidable. This was to be
expected and probably not groundbreaking, but the proofs are nice and elementary
and with lots of pictures.