Algèbres de Hopf combinatoires

Avant-propos

La principale activité en combinatoire algébrique est l’étude de problèmes classiques de combinatoire comme le dénombrement, l’énumération, la génération aléatoire. Cette étude s’appuie sur des méthodes propres à l’algèbre. D’un autre côté, l’étude de structures algébriques utilise des moyens informatiques et des techniques propres à la combinatoire. Ce lien entre algèbre et combinatoire se manifeste dans les constructions algébriques dans lesquelles les structures combinatoires sont mises en jeu.

Un très grand nombre de structures algébriques sont aujourd’hui connues ; chacune d’entre elles possède des caractéristiques permettant de décrire plus ou moins précisément certaines propriétés combinatoires. Il est ainsi naturel de construire des structures algébriques sur divers objets combinatoires.

Contexte

L’une de ces structures qui semblent prometteuses, et celle qui renferme le plus d’informations, est la structure d’algèbre de Hopf. Ces structures se révèlent centrales en combinatoire algébrique [25]. Des références classiques sur le sujet sont [49], [1] et [11]. Des règles de composition et de décomposition sur les objets combinatoires données par des algorithmes combinatoires définissent, lorsqu’elles vérifient un certain nombre de relations de compatibilité, une structure d’algèbre de Hopf combinatoire. Toutes ces structures algébriques s’agencent, la plupart du temps, dans des diagrammes dont les flèches sont des injections ou des surjections. Ces morphismes, souvent donnés par l’intermédiaire d’algorithmes combinatoires mettent en évidence certains liens entre différents objets combinatoires.

Établir des propriétés ou les justifier à partir de ces structures peut s’avérer délicat, et les réalisations polynomiales peuvent apporter des simplifications. L’idée d’une réalisation polynomiale est d’encoder les objets combinatoires par des polynômes de sorte que le produit décrivant l’algèbre de Hopf combinatoire devienne le produit ordinaire des polynômes, et le coproduit est donné par un doublement d’alphabets.

La notion heuristique d’algèbre de Hopf combinatoire contient les algèbres de Hopf graduées dont les bases sont indexées par des objets combinatoires. L’algèbre de Hopf des fonctions symétriques Sym est le prototype même de cette notion. Ses éléments sont des fonctions symétriques [36] et ses bases sont indexées par les partitions d’entiers. Pour certaines bases de Sym, le produit et le coproduit se calculent par l’intermédiaire d’opérations élémentaires sur ces objets. Dans ces dernières années, un grand nombre d’algèbres de Hopf combinatoires furent introduites et étudiées [17], [37], [35], [12], [20], [40, 42], [44] et [21].

Algèbres de Hopf combinatoires

Dans tout ce mémoire, K désigne un corps de caractéristique 0 et nous notons 1K l’élément neutre de K. Toutes les structures algébriques considérées sont définies sur le corps K. Le but de ce paragraphe est de fixer le cadre et les notations des structures algébriques que nous allons rencontrer. Le terme « combinatoire » n’est pas standard et ce terme suppose implicitement que les bases sont indexées par des « objets combinatoires ».

Espaces vectoriels combinatoires

Dans tout ce paragraphe, nous illustrerons les différentes définitions des structures algébriques avec des diagrammes commutatifs et utiliserons les espaces vectoriels suivants comme point de départ à nos premiers exemples :
1. l’espace vectoriel K[X1, . . . , Xn] des polynômes commutatifs en n variables ;
2. l’espace vectoriel K[G] de base les éléments d’un groupe multiplicatif G.

Algèbres de Hopf combinatoires

Une bigèbre est un quintuplet (B, µ, η, ∆, ε) tel que :
1. (B, µ, η) est une algèbre ;
2. (B, ∆, ε) est une cogèbre ;
3. ∆ et ε sont des morphismes d’algèbres.

Une sous-bigèbre de (B, µ, η, ∆, ε) est à la fois une sous-algèbre de (B, µ, η) et une sous-cogèbre de (B, ∆, ε). Un bi-idéal de B est à la fois un idéal de (B, µ, η) et un co-idéal de (B, ∆, ε). Un morphisme de bigèbres est à la fois un morphisme d’algèbres et de cogèbres. Une bigèbre B est commutative (resp. co-commutative) si (B, µ, η) (resp. (B, ∆, ε)) l’est. Une bigèbre B est graduée (resp. combinatoire) si l’algèbre (B, µ, η) et la cogèbre (B, ∆, ε) sont graduées (resp. combinatoire).

Le dual gradué d’une bigèbre combinatoire (B, µ, η, ∆, ε) est la bigèbre combinatoire (B*, µ*, η*, ∆*, ε* ), où B* est le dual gradué de l’espace vectoriel B. Le produit µ* dual du coproduit ∆ et le coproduit ∆* dual du produit µ sont définis par :
hµ*(x ⊗ y), zi = hx ⊗ y, ∆(z)i,
h∆*(x), y ⊗ zi = hx, µ(y ⊗ z)i,

où x, y est le crochet de dualité. Une bigèbre combinatoire B est autoduale si son dual est isomorphe en tant que bigèbre à B. Dans la suite de ce mémoire, nous parlerons simplement de dual pour le dual gradué.

Soit (C, ∆, ε) une cogèbre et (A, µ, η) une algèbre. L’espace vectoriel Hom(C, A) est muni d’une structure d’algèbre. Le produit est défini, pour tout f ∈ Hom(C, A) et g ∈ Hom(C, A), par f ∗ g := µ ◦ (f ⊗ g) ◦ ∆,

et l’unité est donné par l’application x → η ◦ ε(x). L’associativité du produit µ et la co associativité du coproduit ∆ assure l’associativité du produit ∗. L’algèbre (Hom(C, A), ∗, η ◦ ε) est appelée l’algèbre de convolution.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
I Préliminaires
1 Classes et objets combinatoires
1.1 Mots
1.2 Permutations
1.3 Mots tassées
1.4 Fonctions de parking
1.5 Partitions d’un ensemble
1.6 Matrices
2 Algèbres de Hopf combinatoires
2.1 Espaces vectoriels combinatoires
2.2 Algèbres combinatoires
2.3 Cogèbres combinatoires
2.4 Algèbres de Hopf combinatoires
2.5 Réalisations polynomiales
3 Exemples d’algèbres de Hopf combinatoires
3.1 sur des mots
3.2 Sur des partitions
II Permutations de blocs uniformes
1 Permutations de blocs uniformes
1.1 Définitions
1.2 Représentation graphique
1.3 Décomposition via les partitions et permutations
2 Algèbre de Hopf combinatoire
2.1 Définitions
2.2 Réalisation polynomiale
2.3 Propriétés algébriques
III Matrices carrées tassées
1 k-matrices tassées
1.1 Définitions
1.2 Énumérations
2 Structures algébriques
3 Propriétés algébriques
3.1 Bases multiplicatives et liberté
3.2 Éléments primitifs
3.3 Structure de bigèbre bidendriforme
4 Liens avec d’autres algèbres connues
4.1 Algèbre de Hopf des permutations colorées
4.2 Algèbre de Hopf des permutations de blocs uniformes
4.3 Algèbre des fonctions quasi-symétriques matricielles
4.4 Diagramme des plongements
IV Matrices à signes alternants
1 Définitions
1.1 Matrices à signes alternants et objets équivalents
1.2 Statistiques
2 Algèbres de Hopf combinatoires
2.1 ASM
3 Etudes de statistiques
3.1 Interprétations algébriques
3.2 Algèbres quotients
V Outil informatique
Conclusion