Fonctionne avec Indico
v3.2.9
L'un des problèmes les plus fondamentaux en théorie du pavage est le problème du domino : étant donné un ensemble de tuiles, peut-on décider s'il existe un moyen de paver le plan? Depuis les années 60 on sait que ce problème est indécidable en général y compris en se restreignant aux tuiles de Wang, qui sont des tuiles carrées unitaires avec des couleurs sur leurs bords et que l'on peut assembler à condition qu'elles partagent la même couleur sur leur bord commun. Dans cet exposé je présenterai une notion de robustesse pour des jeux de tuiles de Wang : plusieurs jeux de tuiles célèbres de la littérature possèdent cette propriété, et satisfont donc un certain invariant de manière prouvable, et le problème du domino devient décidable pour les jeux de tuiles robustes.
Il s’agit d’un travail en collaboration avec Manon Blanc et Olivier Bournez.