Algèbres de Hopf combinatoires

Les algèbres de Hopf sont des structures algébriques très riches puisqu’elles sont constituées d’un espace vectoriel sur lequel est à la fois défini une structure d’algèbre et une structure de cogèbre. Dans une algèbre, on dispose d’un produit qui permet d’assembler des éléments, et à l’inverse, dans une cogèbre, on dispose d’un coproduit qui permet plutôt de les désassembler. Ces deux opérations doivent vérifier un certain nombre de compatibilités, ce qui fait que les algèbres de Hopf sont, informellement parlant, des structures algébriques extrêmement contraintes. Des références classiques sur le sujet sont entre autres [Swe69], [Abe80], et [Car06].Lorsque l’espace vectoriel sous-jacent à une algèbre de Hopf possède des bases indexées par des objets combinatoires, son produit et son coproduit sont la plupart du temps reformulables en termes d’algorithmes combinatoires. Moyennant quelques conditions supplémentaires, un tel ob- jet est appelé de manière heuristique algèbre de Hopf combinatoire, dont la définition exacte n’est à l’heure actuelle toujours pas fixée — il est intéressant de voir à ce propos [ABS03] ou [LR10] qui donnent chacun de leur coté leur propre définition de ce concept. Ce sont précisément ces objets qui occupent une place de choix dans ce mémoire, et nous proposons nous aussi une dé- finition adaptée à notre contexte. De bonnes introductions aux algèbres de Hopf combinatoires sont [Hiv03] et [Bla10].La littérature dans ce domaine est très abondante : citons par exemple [MR95] (voir égale- ment [DHT02]) où une algèbre de Hopf sur les permutations est introduite, mais aussi [NTT04] et [HNT08a] où des algèbres de Hopf combinatoires sur des graphes étiquetés sont construites et étudiées, ou encore [NT04] et [NT07] où les auteurs construisent une algèbre de Hopf sur les fonctions de parking et plusieurs sous-algèbres de Hopf de celle-ci dont l’une est basée sur les arbres de Schröder et une autre sur les objets catalans. Une grande quantité d’algèbres de Hopf combinatoires mettent en jeu des arbres, parmi lesquelles celle de Loday-Ronco sur les arbres binaires [LR98] (voir aussi [HNT02]), et celle de Connes-Kreimer sur les forêts d’arbres enracinés [CK98] sont sans doute les plus célèbres.

Une manière très avantageuse de voir ces algèbres de Hopf est d’interpréter ses éléments comme des polynômes — commutatifs ou non. Le produit de l’algèbre devient un simple pro- duit polynomial, et le coproduit de la cogèbre étant obtenu par une transformation d’alpha- bet [KLT97] adéquate. Cette manière de voir les choses simplifie considérablement la théorie puisque la plupart des produits, définis sur les objets combinatoires eux-mêmes, peuvent être a priori extrêmement complexes, en contraste avec la simplicité du produit de polynômes offerte a posteriori par une réalisation polynomiale. De plus, la compatibilité entre le produit et le copro- duit, propriété essentielle dans une algèbre de Hopf, devient immédiate. On appelle ce procédé une réalisation polynomiale d’une algèbre de Hopf. Plusieurs algèbres de Hopf combinatoires ont été ainsi réalisées : l’algèbre de Hopf des permutations [DHT02], celle de Loday-Ronco des arbresCe chapitre préliminaire est organisé comme suit. Nous commençons en donnant dans le paragraphe 2.1 la définition de plusieurs structures algébriques : les algèbres associatives, les cogèbres, et les bigèbres, ainsi que les notions de base qui s’y rattachent. Nous terminons ce paragraphe en formalisant dans notre contexte la notion de réalisation polynomiale d’une al- gèbre de Hopf. Finalement, les concepts présentés sont illustrés dans le paragraphe 2.2 par des exemples. Nous passons ainsi en revue l’algèbre de Hopf de mélange et de déconcaténation, l’algèbre de Hopf de Connes-Kreimer, et l’algèbre de Hopf de Malvenuto-Reutenauer.

La plupart des algèbres combinatoires s’implantent facilement, par exemple en Sage [S11]. Il suffit en effet de spécifier la classe combinatoire sous-jacente et de programmer le produit de deux éléments de base. Le système étend automatiquement le produit par linéarité. Un bon nombre d’implantations ont été réalisées dans ce travail pour des expérimentations. Remarquons que la notion de cogèbre est en un certain sens duale de la notion d’algèbre. En effet, on obtient le diagramme (2.1.21) en inversant le sens des flèches du diagramme (2.1.3). Il en est de même pour le diagramme (2.1.22) qui peut être obtenu de la même façon à partir du diagramme (2.1.4). Ainsi, les notions définies dans le paragraphe 2.1.1 sont adaptables aux cogèbres. Reformulons-les tout de même.11]. Il suffit en effet de spécifier la classe combinatoire sous-jacente et de programmer le coproduit d’un élément de base. Le système étend automatiquement le coproduit par linéarité. Un bon nombre d’implantations ont été réalisées dans ce travail pour des expérimentations.