Jeudi 12 novembre 2026, 14:00 à 15:00

salle des séminaires du département d'informatique

Louis Lachaize

(LISN, Université Paris-Saclay)

On s’intéresse à certains pavages du plan : des colorations de la grille Z^2 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-il possible de colorier le plan tout entier ? 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 de M2 encadré Benjamin Hellouin de Menibus au LISN (Université Paris-Saclay). 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.