On étudie les shifts ou espaces de pavages de type fini: des colorations de la grille régulière infinie qui évite 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, de nombreuses 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é une coloration partielle, est-il possible de la compléter en une coloration de la grille 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 cocyles 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.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne