Factorisations des mots de basse complexité

Nous présentons dans ce doctorat de mathématiques le travail effectué pendant trois ans à l'Université Claude Bernard Lyon 1. Ce doctorat a été réalisé sous les directions de Boris Adamczewski et Luca Zamboni, tous deux chercheurs à l'UCBL. Le thème général abordé est la combinatoire des mots, sous la forme de deux contributions, l'une concernant la théorie de Ramsey développée dans la première partie, et l'autre la classe des mots sturmiens développée dans la seconde partie. La combinatoire des mots est un domaine à la croisée des mathématiques, et plus généralement des sciences. Avec l'essor de l'informatique théorique, ou encore des progrès de la génétique, l'étude des suites de symboles est devenu un sujet de recherche incontournable à l'importance grandissante. Les mots vus comme suites de symboles sont en effet intrinsèquement soumis à des lois mathématiques d'une profonde subtilité. L'exemple historique d'Axel Thue d'un mot infini sans facteurs carrés sur un alphabet à trois lettres a été un des points de départ de cette théorie, via une construction non-triviale d'un mot infini soumis à une condition pourtant très simple en apparence. Que ce soit dans la structure des décimales des nombre réels, dans les codes informatiques omniprésents dans le fonctionnement des ordinateurs, ou dans notre propre code génétique, la combinatoire des mots fournit un cadre commun pour une étude en profondeur de problématiques actuelles. Le présent doctorat s'inscrit naturellement dans ce processus scientifique. Directement inspiré par les travaux fondateurs d'Axel Thue, nous étudions dans la première partie les conditions d'existence d'objets combinatoires (en outre, des colorations) soumis à des contraintes d'apparence simples, et nous apportons une réponse optimale à une conjecture qui est restée ouverte pendant une décennie. Cette solution exploite les différences et liens entre les notions naturelles de préfixe et de suffixe en combinatoire des mots. Notre seconde partie, quant à elle, étudie une version infinie du système de numération d'Ostrowski, à l'aide des mots de basse complexité donnés par les mots infinis non-ultimement périodiques de plus petite fonction de complexité que sont les mots sturmiens. Construit d'une manière analogue aux nombres p-adiques, le formalisme introduit et développé concernant les intercepts formels en vue de donner une description combinatoire de la classe des mots sturmiens a pour conséquences plusieurs résultats concernant les factorisations de ces mots. Le calcul des compléments étudié à la fin de cette partie montre comment la comparaison des opérations de préfixe et de suffixe peut être utilisée pour obtenir des résultats non-triviaux concernant les factorisations des mots de basse complexité