Combinatoire des mots : mots parfaitement amassants, triplets de Markoff et graphes chenilles

Lapointe, Mélodie (2020). « Combinatoire des mots : mots parfaitement amassants, triplets de Markoff et graphes chenilles » Thèse. Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en mathématiques.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (929kB)

Résumé

Dans cette thèse, nous étudions divers problèmes de combinatoire des mots. Ces problèmes sont en lien avec les systèmes dynamiques, le groupe libre, les nombres de Markoff et la théorie des graphes. D’abord, nous étudions les mots parfaitement amassants, une généralisation des mots de Christoffel sur un alphabet ordonné quelconque. Un mot est parfaitement amassant si sa transformée de Burrows-Wheeler est un mot décroissant. Nous proposons deux nouvelles façons de construire ces mots. D’abord, nous généralisons l’arbre de Raney, c’est-à-dire l’arbre binaire complet infini étiqueté par les fractions réduites, pour obtenir un arbre infini étiqueté par les compositions correspondant à l’image commutative des mots parfaitement amassants. Ensuite, nous proposons un ensemble d’automorphismes du groupe libre engendrant l’ensemble des mots parfaitement amassants. Ces automorphismes permettent de construire l’arbre des mots parfaitement amassants. De plus, nous démontrons que les mots parfaitement amassants sont des éléments primitifs positifs du groupe libre. Ensuite, nous étudions les triplets de Markoff et la conjecture de Frobenius. Nous proposons d’abord une bijection entre les mots binaires et les triplets de Markoff qui utilise des fonctions de palindromisation. La conjecture de Frobenius suggère que les nombres de Markoff apparaissent comme maximums d’un seul triplet de Markoff. Plusieurs formulations équivalentes sont connues, en particulier en combinatoire des mots. Nous généralisons cette conjecture et nous démontrons que ces généralisations sont valides sur certains sous-ensembles de mots. Finalement, nous présentons une nouvelle relation entre les mots préfixes normaux et la théorie des graphes. Les mots préfixes normaux sont les mots binaires sur l’alphabet {0, 1}* dont tout préfixe contient plus de 1 que tous ses facteurs de même longueur. Les mots préfixes normaux sont en bijection avec les mots feuillus des graphes chenilles, c’est-à-dire les graphes tels que le sous-graphe induit par tous les sommets sauf les feuilles est une chaine simple. Le mot feuillu d’un graphe est la dérivée discrète de la fonction dont l’image est le nombre maximal de feuilles d’un sous-graphe induit ayant k sommets. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Mots de Christoffel, Mot parfaitement amassants, Échange d’intervalles discrets symétriques, Automorphismes, Triplets de Markoff, Conjecture de Frobenius, Mots préfixes normaux, Mots feuillus, Graphes chenilles

Type:	Thèse ou essai doctoral accepté
Informations complémentaires:	Fichier numérique reçu et enrichi en format PDF / A.
Directeur de thèse:	Blondin Massé, Alexandre
Mots-clés ou Sujets:	Combinatoire des mots / Mots parfaitement amassants / Mots de Christoffel / Triplets de Markov / Graphes chenilles
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Service des bibliothèques
Date de dépôt:	24 mars 2021 13:36
Dernière modification:	24 mars 2021 13:36
Adresse URL :	http://archipel.uqam.ca/id/eprint/14120

Modifier les métadonnées (propriétaire du document)

Statistiques