Soutenance mémoire
Algèbres de Hopf
Les algèbres de Hopf sont une généralisation possible des séries génératrices qui permettent d’enregistrer une information plus fine (comme une liste arbitrairement longue de nombres, une permutation, un arbre, etc.). Par exemple, pour compter les permutations en fonction des classes de descentes (qui sont un sous-ensemble de l’ensemble {1, . . . , n}, Gessel introduit l’algèbre des fonctions quasi-symétriques QSym [Ges83]. La duale de cette algèbre est introduite par les six auteurs Gelfand, Krob, Lascoux, Leclerc, Retakh et Thibon en tant qu’algèbre des fonctions symétriques non-commutatives NCSF [GKL+95]. Les algèbres de Hopf sont des structures formelles dont les bases sont indexées par des objets combinatoires. Dans une telle algèbre, le produit (comme dans les algèbres classiques) correspond à une façon d’assembler des objets et le coproduit à une façon de désassembler ces mêmes objets. Pour guider l’intuition du lecteur, prenons un jeu de cartes. L’ensemble de toutes les coupes possibles (somme formelle) de ce jeu de cartes correspond à un coproduit. Maintenant, supposons que notre paquet de cartes soit déjà coupé en deux paquets plus petits, l’ensemble de toutes les possibilités de mélange américain (somme formelle) de ces deux paquets correspond au produit dans l’algèbre de Hopf. C’est l’idée qui sous-tend la définition de l’algèbre de Hopf FQSym [MR95, DHT01] dont la base est indexée par les permutations. Dans la suite du manuscrit, nous étudierons cette algèbre de façon détaillée. Voici un exemple du produit de mélange (inspiré du mélange des cartes) et du coproduit correspondant. Dans le produit, on remarque en particulier que l’ordre de 1 et 2 (en noir) reste toujours le même ainsi que l’ordre de 3 et 4 (en rouge). Cet exemple est repris et expliqué plus en détail dans l’exemple 1.25.
Combinatoire des mots tassés et des arbres biplans
Dans toute la combinatoire en lien avec les algèbres de Hopf, par exemple sur les permutations ou les mots, l’idée de “décomposition” est fondamentale. On cherche à décomposer au maximum les objets combinatoires pour obtenir des éléments dits “irréductibles” qui permettent d’engendrer les éléments de l’algèbre. C’est le cas par exemple de la décomposition en descentes globales sur les permutations, définie par Aguiar et Sottile [AS05], que nous avons généralisée aux mots tassés. La décomposition en descentes globales d’un mot est unique et tous les facteurs sont dits irréductibles (voir figure 2). Parmi les nombreuses bases connues de WQSym, certaines sont dites multiplicatives et le produit est défini par la concaténation décalée des indices (voir le paragraphe 2.7 de [NT06] pour des exemples). On peut en déduire que le nombre de mots tassés irréductibles de taille n est égal à la dimension de l’espace des primitifs de l’algèbre au degré n. Cependant, si l’on souhaite définir des bases compatibles avec la structure bidendriforme, on a besoin d’un découpage supplémentaire de ces éléments irréductibles. En effet, on souhaite définir une famille d’éléments dits “totalement irréductibles” qui puisse indicer une base des “espaces des totalement primitifs”. Pour mener à bien cette recherche, nous avons créé deux opérations binaires I et N qui agissent sur les mots tassés (voir lemme 6.6). L’opération I donne un sens particulier à la position des maximums et l’opération N donne un sens particulier à la valeur de la dernière lettre. La concaténation décalée / est à la décomposition en descentes globales ce que l’opération I (resp. N) est à la décomposition rouge (resp. bleu). Nous avons donc défini deux nouvelles décompositions des mots qui font intervenir ces nouvelles opérations. Nous avons défini les mots irréductibles rouges (resp. bleus) comme les mots irréductibles ne pouvant pas s’écrire sous la forme uIv (resp. uNv). Nous avons enfin prouvé que les cardinaux de ces ensembles sont égaux aux dimensions de “l’espace des totalement primitifs”. Pour décrire ces décompositions, nous avons introduit une nouvelle famille d’objets combinatoires : les forêts d’arbres biplans. Les décompositions précédentes appliquées récursivement permettent de prouver les bijections suivantes :
— Les forêts biplanes et les mots tassés,
— Les arbres biplans et les mots tassés irréductibles,
— Les arbres biplans sans fils gauche à la racine et les mots tassés irréductibles rouges ou bleus (en fonction de la couleur de l’arbre).
Chaque “branche” d’un arbre correspond, d’une part du point de vu combinatoire, à une opération sur les mots eux-mêmes, et d’autre part, à une opération algébrique compatible avec la structure bidendriforme.
Grammaires et séries génératrices
Nous avons défini précédemment plusieurs classes combinatoires : permutations, permutations irréductibles, mots tassés, mots tassés irréductibles, arbres binaires, arbres plans, forêts d’arbres plans, arbres décorés. Nous avons donné des tables montrant les cardinalités de la plupart de ces objets par taille (tables 1.1, 1.2, 1.3, 1.4 et 1.5). Flajolet et Sedgewick font le lien entre les grammaires symboliques et les séries génératrices [FS09, Figures I.18 et II.18]. Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c’est-à-dire un ensemble de mots admissibles sur un alphabet donné. Une grammaire se caractérise par un ensemble fini de symboles, terminaux ou non, et un ensemble de règles de productions.
Ordres sur les mots tassés
Dans cette section nous allons nous intéresser à 4 ordres partiels sur les mots tassés. Pour 3 de ces ordres, il s’agit de généralisations des ordres faibles sur les permutations. Ce sont des généralisations dans le sens où la restriction aux permutations décrit bien l’ordre faible et que c’est un sous-poset. Plus de détails et de propriétés sur ces ordres sont présentés dans [Var19, KLNP01]. Les produits de mélange sur les mots tassés sont visibles sur des intervalles de ces 3 ordres. Nous avons en effet bien défini 3 types de produits de mélange sur les mots tassés : mélange des positions, mélange des valeurs et mélange des valeurs sans chevauchement. Nous nommerons respectivement ces trois ordres : ordre faible droit, ordre faible gauche avec chevauchement et ordre faible gauche.
Généralisation de l’inversion
Quand on regarde FQSym, qui est l’algèbre de Hopf indexée par les permutations, l’inversion des permutations constitue un isomorphisme bidendriforme de cette algèbre (équation (3.26)). Ce qui était complexe avec WQSym, c’est que l’inversion des mots tassés n’était pas définie. Néamoins, notre construction a permis d’obtenir un isomorphisme bidendriforme. Dans celle-ci, la restriction aux permutations ne correspond pas à l’inversion. En particulier, pour les permutations irréductibles rouges et bleus, comme pour tous les mots tassés irréductibles rouges et bleus, nous avons choisi l’identité pour ne pas faire des permutations un cas particulier. Nous aurions pu choisir de prendre l’inversion pour ces permutations précises, notre construction aurait alors donné l’inversion pour toute les permutations et aurait permis de s’approcher d’une certaine compatibilité avec l’inversion des permutations. La question qui se pose alors est la suivante : existe-t-il une généralisation de l’inversion des permutations pour les mots tassés ? Notre travail a l’intérêt de réduire le champ de recherche au sous-ensemble des mots tassés irréductibles rouges et bleus.
Généralisation de la théorie des arbres biplans
L’algèbre PQSym indexée par les fonctions de parking est très similaire à WQSym, mais aussi plus complexe et son étude serait un premier pas vers la généralisation de la théorie des arbres biplans. En effet PQSym est également une bigèbre bidendriforme et les fonctions de parking sont un sur-ensemble des mots tassés. La question de généraliser la théorie aux fonctions de parking relève à la fois de la combinatoire et de l’algèbre. Nous avons eu l’occasion de travailler avec Aaron Lauve et Amy Pang, qui cherchaient s’il existait une base de PQSym dans laquelle le produit de mélange était sans chevauchement. Nous avons au moins une piste de recherche prometteuse, mais non présentable en son état actuel. Les résultats de cette recherche pourraient faire l’objet d’un notebook similaire à ceux présentés dans la partie IV. La construction de ce changement de base serait aussi le premier ingrédient nécessaire pour généraliser la théorie des arbres biplans sur PQSym. Les pistes de recherche induites par ce travail sont les suivantes : comment généraliser la théorie des arbres biplans sur PQSym ? On pourra aussi s’intéresser aux matrices tassées et encore généraliser toutes les constructions de la partie II à toutes bigèbres bidendriformes. On cherchera alors quels sont les ingrédients nécessaires et suffisants pour développer la théorie des arbres biplans et obtenir un auto-morphisme bidendriforme.
Une algèbre Bigraft sur les mots tassés
Enfin il est possible de s’intéresser à l’opérade bigraft sous-jacente.
Proposition 7.21. L’ensemble des mots tassés muni des opérations /, I et H forme une algèbre bigraft. Cette algèbre est engendrée par les mots tassés à la fois rouges-irréductibles et bleus-irréductibles, avec une seule relation : uI1 = 1Hu.
Démonstration. Le fait que les mots tassés soient engendrés par les mots tassés à la fois rouges-irréductibles et bleus-irréductibles en tant qu’algèbre bigraft est une conséquence direct des propositions 7.18 et 7.20. Enfin, d’après le théorème 6.16 comme il y a une bijection entre les forêts d’arbres rouges-bleus-tassés et les mots tassés, la seule relation est uI1 = 1Hu. Preuve de la proposition 7.12. On observe immédiatement qu’il existe des morphismes d’opérades depuis les opérades dupliciales déformées gauche et droite et l’opérade de Lalgèbre vers l’opérade bigraft. Cela signifie que les algèbres bigrafts sont des algèbres dupliciales déformées gauche et droite et des L-algèbres. Pour prouver l’injectivité de ces morphismes, observont une algèbre bigraft sur les mots tassés en prenant un unique générateur. Pour éviter la relation uI1 = 1Hu, prenons le mot tassé 11 comme générateur. L’algèbre bigraft engendrée par le mot tassé 11 est libre, or ce qui est généré par 11 comme algèbre dupliciale déformée gauche ou droite ou comme L-algèbre est aussi libre d’après les propositions 7.18 et 7.20. Il n’y a pas d’autres relation, le morphisme d’opérade est donc injectif.
|
Table des matières
I Préliminaire
1 Objets combinatoires
1.1 Mots
1.1.1 Définitions utilitaires
1.1.2 Permutations
1.1.3 Mots tassés
1.2 Forêts et arbres
1.2.1 Arbres binaires et arbres plans
1.2.2 Décorations des arbres
1.2.3 Greffes d’arbres
1.3 Grammaires et séries génératrices
2 Ordres partiels
2.1 Définitions
2.2 Ordres faibles sur les permutations
2.2.1 Groupe symétrique
2.2.2 Ordres faibles droit et gauche
2.3 Ordres sur les mots tassés
2.3.1 Généralisation de l’ordre faible droit
2.3.2 Deux généralisations de l’ordre faible gauche
2.3.3 Ordre de raffinement
3 Algèbres de Hopf combinatoires
3.1 Définitions générales
3.2 Exemples d’algèbres de Hopf combinatoires
3.2.1 L’algèbre FQSym
3.2.2 L’algèbre WQSym
3.2.3 L’algèbre HD P,R
3.3 Bigèbres bidendriformes
3.3.1 Définitions
3.3.2 Reprise des exemples
3.3.3 Théorème de Cartier-Milnor-Moore pour les bigèbres bidendriformes
II Automorphism of WQSym
4 Combinatorics of biplane forests
4.1 Dual (Red)
4.1.1 Decomposition of packed words through maximums
4.1.2 Red-forests from decomposed packed words using φ
4.2 Primal (Blue)
4.2.1 Decompositions of packed words through last letter
4.2.2 Blue-forests from decomposed packed words using ψ
4.3 Intervals for half shuffle products
5 Bases for totally primitive elements
5.1 Dual (Red)
5.1.1 Decomposition through maximums and totally primitive elements
5.1.2 The new basis P
5.2 Primal (Blue)
5.2.1 Decomposition through last letter and totally primitive elements
5.2.2 The new basis O
6 Isomorphism between WQSym and WQSym∗
6.1 A combinatorial solution to an algebraic problem
6.2 Full decomposition of packed words into bicolored forests
6.3 An involution on packed words
6.4 Main theorem
III Autour de WQSym, résultats et perspectives
7 Opérades et mots tassés
7.1 Rappels sur les opérades
7.1.1 Définitions de bases
7.1.2 Exemples d’opérades
7.1.3 Algèbre sur une opérade
7.2 Une algèbre dupliciale déformée sur les mots tassés
7.3 Une L-algèbre sur les mots tassés
7.4 Une algèbre Bigraft sur les mots tassés
IV Expérimentation avec SageMath
8 Notebooks en ligne
8.1 Objets combinatoires
8.1.1 Mots tassés
8.1.2 Arbres biplans
8.2 Ordres partiels
8.3 Bases de WQSym
8.4 Autres bases de WQSym
8.5 Séries génératrices
Télécharger le rapport complet
