Problème du domino pour les homshifts généralisés (ou H-coloration de graphes de Cayley)
Time: 14:00 -- Location: bat 650, 455
summary: On s’intéresse à certains pavages du plan : des colorations de la grille
Z² par un nombre fini de couleurs, et respectant un certain nombre de
contraintes. Le problème du domino est le suivant : étant donné un
nombre fini de motifs interdits, est-ce qu’il est possible de colorier
le plan tout entier en évitant ces motifs ? Il a été prouvé en 1964 que
ce problème est indécidable ; il n’existe aucun algorithme capable de le
résoudre.
On modifie alors les règles pour rendre le modèle plus simple. On impose
que les motifs interdits soient locaux (concernent seulement deux cases
côte à côte) et isotropes (les motifs interdits sont les mêmes dans
toutes les directions). Ce modèle s’appelle homshift, et le problème du
domino devient beaucoup plus simple puisqu’il est presque toujours
possible de trouver un pavage valide.
Pendant l’exposé, je vais vous présenter les résultats de mon stage avec
Benjamin Hellouin. Nous nous sommes intéressés à une classe
intermédiaire entre les homshifts et le cas général, dans laquelle on
conserve l’isotropie mais pas le caractère local. Une manière de
reformuler le problème fait intervenir la H-coloration de graphes de
Cayley.