Treillis sur les arbres binaires et algèbres de Hopf

La troisième partie de ce mémoire est dédiée à l’étude d’un ordre sur les arbres binaires appelé treillis de Tamari qui peut se décrire comme un quotient de l’ordre faible sur les permutations. Il apparaît en 1962 dans le travail de Tamari [Tam62] sous forme de structure d’ordre sur les parenthésages formels d’une expression. Tamari prouve plus tard que cet ordre est en fait un treillis [HT72]. Par ailleurs, son diagramme de Hasse correspond à un polytope connu sous le nom d’associaèdre ou polytope de Stasheff. Le nombre de parenthésages formels d’une expression est compté par les nombres de Catalan et il existe donc de multiples objets combinatoires sur lesquels on peut décrire ce treillis [Sta99]. Dans ce chapitre, nous en rappelons deux : les chemins de Dyck et les arbres binaires. Dans les deux cas, la relation de couverture se décrit par une opération très simple (cf. figures 6.1 et 6.4). Les relations entre l’associaèdre et le permutoèdre sont souvent étudiées d’un point de vue géométrique. L’approche algébrique permet de démontrer un résultat très fort : l’ordre de Tamari est un quotient de l’ordre faible sur les permutations. Ce résultat apparaît déjà en filigrane dans les travaux de Björner et Wachs [BW91]. On en trouve une généralisation dans la théorie des treillis cambriens de Reading [Rea06]. Une explication directe est donnée dans [HNT05]. Ce dernier article ainsi qu’un précédent de Loday et Ronco [LR98] font le lien avec une structure importante en combinatoire algébrique : les algèbres de Hopf. Le principe d’une structure d’algèbre est la composition des objets. C’est-à-dire que si A est un espace vectoriel d’objets combinatoires, on définit une application A ⊗ A → A. Si maintenant on définit une opération dite de coproduit : A → A ⊗ A et qu’elle vérifie une certaine compatibilité avec le produit, on obtient une structure de bigèbre. En termes combinatoires, cela revient à décomposer les objets. Dans le cadre de la topologie algébrique du milieu du XXème siècle, Heinz Hopf étudia certaines bigèbres possédant une opération appelée antipode qui généralise la notion de passage à l’inverse des groupes. C’est ce qu’on appelle 117 Treillis sur les arbres binaires et algèbres de Hopf 118 Chapitre 6 — Treillis sur les arbres binaires et algèbres de Hopf les Algèbres de Hopf [Swe69, Car07]. En combinatoire, c’est surtout la structure de bigèbre qui est intéressante. Comme on travaille dans des espaces de dimension finie graduellement, l’existence de l’antipode est toujours vérifiée et on appelle donc ces espaces des algèbres de Hopf combinatoires. Cette double structure de produit et coproduit est déjà implicitement présente dans le travail de MacMahon sur les fonctions symétriques [Mac60]. Puis dans les années 1970, Rota fait le lien avec la structure étudiée par les topologues et insiste sur l’importance des algèbres de Hopf en combinatoire [JR79, Rot78]. On pourra lire [Hiv07] pour une bonne introduction sur le sujet. La théorie des algèbres de Hopf combinatoires prend une nouvelle direction avec l’apparition en 1995 des fonctions symétriques non-commutatives qui feront l’objet d’une série d’articles sur plus de dix ans [GKL+95, KLT97, DKKT97, KT97, KT99, DHT02, DHNT11]. C’est en fait une nouvelle méthode de calcul qui est décrite : à un objet combinatoire, on associe une somme de mots sur un alphabet non commutatif. Le produit et le coproduit ne se définissent plus sur les objets mais sur les mots ce qui en fait des opérations triviales. La difficulté réside alors dans la fonction qui à chaque objet associe une somme. C’est ce qu’on appelle la réalisation polynomiale. Elle permet souvent de trivialiser des preuves jusqu’alors complexes et de donner le cadre pour des résultats plus importants. En particulier, dans [DHT02, DHNT11] les auteurs introduisent l’algèbre des fonctions quasi-symétriques libres FQSym dont les bases sont indexées par les permutations. Cette algèbre se révèle isomorphe à une algèbre de Hopf déjà connue sur les permutations, celle introduite par Malvenuto et Reutenauer [MR95].

Treillis de Tamari et ordre faible 

Définition : chemins de Dyck et arbres binaires

La définition historique de l’ordre de Tamari est donnée en termes de parenthésages. Nous donnons ici celle en termes de chemins de Dyck qui est couramment utilisée. Définition 6.1.1. Un chemin de Dyck de taille n est un chemin dans le plan depuis l’origine jusqu’au point (2n, 0) formé de pas dits « montants » (1, 1) et de pas « descendants » (1, −1) tel que le chemin ne descend jamais en dessous la ligne y = 0. On identifie les chemins à des mots sur un alphabet binaire {1, 0} où les pas montants sont représentés par des 1 et les pas descendants par des 0. On les appelle alors mots de Dyck. Ils contiennent autant de 1 que de 0 et et dans chacun de leurs préfixes, le nombre de 1 est supérieur ou égal au nombre de 0. Un chemin est dit primitif s’il n’a pas d’autres contacts avec la droite y = 0 que son origine et son point final. Définition 6.1.2. Soit u un chemin de Dyck, tel que u contienne un pas descendant d suivi d’un chemin primitif c. Une rotation sur u consiste à échanger le pas descendant d avec le chemin c. L’opération de rotation, illustrée figure 6.1, est la relation de couverture de l’ordre de Tamari. C’est-à-dire qu’un chemin v est plus plus grand qu’un chemin u si on peut atteindre v par une série de rotations sur u. Cela définit bien un ordre et même un treillis [HT72], cf. figure 6.2.