Agenda de l'ENS de Lyon

Preuves aidées par ordinateur en combinatoire des mots

Soutenance HDR

Mardi 27 June 2017
10h00
Résumé d'Habilitation à Diriger des Recherches de Michaël RAO (Section CNU n° 27 - Informatique)

Intervenant(s)

Résumé d'Habilitation à Diriger des Recherches de Michaël RAO (Section CNU n° 27 - Informatique)

Description
– Je présente dans ce mémoire une sélection de mes travaux depuis ma prise de poste au CNRS, qui est composé de trois parties.
– Les deux premières parties portent sur la combinatoire des mots, et sont dans la continuation des travaux de Thue, c'est-à-dire sur l'évitabilité de répétitions dans les mots.
– La première partie est dédiée à la conjecture de Françoise Dejean, énoncée en 1972, qui connu beaucoup d'intérêt jusqu'à sa démonstration complète en 2009. Je présente ma preuve pour les derniers cas de la conjecture, qui est ensuite utilisée pour prouver d'autres généralisations. Je conclus cette partie par des questions ouvertes sur le thème de cette conjecture.
– La deuxième partie du mémoire est dédiée à l'évitabilité des répétitions abéliennes, ainsi que leurs généralisations. Les questions abordées sont motivées par des d'Erdös de 1957, et de Mäkelä en 2003.
– Je présente dans cette partie nos résultats (avec Matthieu Rosenfeld) sur l'évitabilité des grandes répétitions abéliennes. Puis je donne des résultats optimaux sur l'évitabilité de deux généralisations récentes : les répétitions k-abéliennes (introduites par Karhumãki et al.) et les répétitions k-binomiales (introduites par Rigo et Salimov).
– Enfin, la troisième partie expose deux résultats que l'on peut rapprocher à des problèmes de mots en dimension deux: la démonstration d'une conjecture de Chang de 1992, stipulant la taille minimum d'un ensemble dominant d'une grille, et la présentation d'un jeu de 11 tuiles de Wang apériodique, qui est le plus petit possible.
Complément

à l'Amphi. A, au 4ème étage

Disciplines