Séminaires SymPA à venir
Séminaires les mardi à 14h en salle BC101.
Organisé par France Gheeraert, Valentin Huguin
We study homshifts: colourings of the regular infinite grid that avoid a finite set of forbidden patterns that are small and the same in every direction.
Homshifts are a restriction of the classical model of shifts of finite type. In contrast to the general case, where more or less everything is undecidable, many questions become tractable. The frontier between the decidable and undecidable problems in this model is still very much open.
I will talk about a series of recent results around the following problem: given a partial coloring, is it possible to complete it into a colouring of the entire grid (while avoiding forbidden patterns?).
This trip will take us through various mathematical vistas: homotopy of finite graphs, families of mixing properties, fundamental groups and cocycles of shifts, and some surprise backdoor undecidability results.
This talk comes from joint works with Nishant Chandgotia, Silvère Gangloff and Piotr Opocha.
Oratrices et orateurs :
- Marie-Pierre Béal, LIGM Université Gustave Eiffel
- Michel Davydov, LMPA Université du Littoral Côte d'Opale
- Martin Leguil, CMLS École Polytechnique
- Barbara Schapira, IMAG Université de Montpellier