The Domino problem on rhombus-shaped tiles.

-- Benjamin Hellouin de Menibus (LISN, Galac)

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.

Category: seminars
Tags: Team seminar combinatorics