Accès direct au contenu

 

logo du site ENS

Logo du site Ens Lyon

Recherche
30 ans de l'ENS de Lyon

Accueil  >  ENS de Lyon > Recherche > HDR >  HDR sc. exactes et exp.

Imprimer

Preuves aidées par ordinateur en combinatoire des mots

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

Lieu(x) :

Site Monod - 46 allée d'Italie
à l'Amphi. A, au 4ème étage
     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.

Retour au haut de la page

Pôle Recherche
 
 
Mise à jour le 21 juin 2017
Ens de Lyon
15 parvis René Descartes - BP 7000 69342 Lyon Cedex 07 - FRANCE
Tél. : Site René Descartes (siège) : +33 (0) 4 37 37 60 00 / Site Jacques Monod : +33 (0) 4 72 72 80 00