Compléter des colorations partielles de hom shifts
Time: 14:00 -- Location: bat 650, 455
summary: On étudie les shifts ou espaces de pavages de type fini : des colorations de la grille régulière infinie qui évitent un ensemble fini de motifs interdits. Il s'agit d'un modèle étudié en particulier comme source apparemment infinie de problèmes indécidables.
Les hom shifts sont une restriction du modèle où les motifs interdits sont petits et isotropes (indépendants de la direction). Par contraste avec le cas général, denombreuses questions deviennent résolubles. La frontière entre problèmes décidables et indécidables est toujours largement ouverte.
Je parlerai d'une série de résultats autour de la question suivante : étant donnée une coloration partielle, est-il possible de la compléter en une coloration de lagrille entière (en évitant les motifs interdits) ? Cette question nous fera voyager à travers plusieurs panoramas mathématiques : homotopie des graphes finis, propriétés de mélange, groupes fondamentaux et cocycles des shifts, et des résultats d'indécidabilité qui reviennent par surprise.
Cet exposé est issu de travaux en commun avec Nishant Chandgotia, Silvère Gangloff, et Piotr Opocha.