Outils

Agenda de l'ENS de Lyon

Autour du problème du domino -Structures combinatoires et outils algébriques

Date
mer 15 juil 2020
Horaires

15H30

Intervenant(s)

Soutenance de M. MOUTOT Etienne du LIP sous la Direction de M. Stephan THOMASSE et la Co-Direction de M. Jarkko KARI (Université de Turku, Finlande)

Organisateur(s)
Langue(s) des interventions
Description générale

Étant donné un ensemble fini de tuiles carrés, le problème du domino est la question : « est-il possible de paver le plan entier en utilisant ces tuiles ? » Ce problème est connu pour être indécidable dans le cas des pavages du plan, et est très fortement lié à la question de la périodicité des pavages. Dans cette thèse nous abordons ce problème de deux point de vue différent: en le généralisant aux structures structures plus générales des groupes, et en regardant le cas particulier des pavages de faible complexité.

Le problème du domino peut se formuler dans le cadre plus général des graphes de Cayley de groupes. Dans cette thèse nous développons de nouvelles techniques permettant de relier les graphes de Cayley de certains groupes à des graphes de substitutions. Une première technique nous permet de montrer qu'il existe à la fois des pavages fortement apériodiques et faiblement-non-fortement apériodiques pour les groupes de Baumslag-Solitar . Une seconde nous permet de montrer que le problème du domino est indécidable pour les groupes de surface, ce qui fourni une nouvelle classe de groupe vérifiant la conjecture disant que que le problème du domino d'un groupe est décidable si et seulement si le groupe est virtuellement libre.

Un pavage du plan est dit de faible complexité s'il y apparaît moins de   rectangles de taille  . Nivat conjecture en 1997 qu'un tel pavage est nécessairement périodique, avec comme conséquence que le problème du domino serait décidable pour les pavages de faible complexité. En continuant de développer des outils algébriques introduits par Kari et Szabados, nous prouvons une version généralisée de la conjecture de Nivat pour une classe de pavage particuliers (certains des sous-décalage algébrique). Nous parvenons également à montrer que la conjecture de Nivat est vraie pour tout pavage uniformément récurrent, avec comme conséquence que le problème du domino est effectivement décidable pour les pavages de faible complexité.

Gratuit

Mots clés

Disciplines