Le monoïde de Baxter

Il existe une large gamme de monoïdes définis en tant que quotients du monoïde libre et dont les classes d’équivalence sont indexées par des objets combinatoires. Le premier exemple historique et sans doute le plus fondamental, est le monoïde plaxique [LS81], [Lot02]. Une définition de ce monoïde repose sur la donnée d’une congruence sur les mots obtenue à partir des relations de Knuth [Knu70]. Une autre approche, plus algorithmique, consiste à partir de l’algorithme de Schensted [Sch61], qui permet de déterminer sur l’entrée d’un mot, la longueur de son plus long sous-mot croissant. Cet algorithme construit un effet un tableau de Young à partir d’un mot, et il est naturel de considérer que deux mots sont équivalents s’ils produisent le même tableau lorsqu’on les insère. Il s’avère que ces deux approches mènent à la construction du même monoïde, que les éléments de ce dernier peuvent s’interpréter comme des tableaux de Young et que le produit du monoïde se calcule par l’intermédiaire de l’algorithme de Schensted. La principale illustration de l’importance du monoïde plaxique est son intervention dans la démonstration de la règle de Littlewood-Richardson [LR34] pour calculer les coefficients qui apparaissent lors de la multiplication de deux fonctions de Schur [Mac95]. Il permet de plus de construire une généralisation de l’algèbre des fonctions symétriques [Mac95] en la plongeant dans l’algèbre des tableaux de Young, rendant plus limpides certaines propriétés des fonctions symétriques. Plus récemment, d’autres monoïdes qui ont des caractéristiques semblables au monoïde plaxique ont été introduits et étudiés. L’exemple le plus convaincant est dans doute le monoïde sylvestre [HNT02], [HNT05], qui, tout comme le monoïde plaxique, peut être défini de deux manières équivalentes, soit par une congruence sur les mots, soit par un algorithme d’insertion. Dans ce cas, c’est l’algorithme d’insertion dans un arbre binaire de recherche [AU94], [Knu98], [CLRS03] qui joue le rôle de l’algorithme de Schensted, et les objets du monoïde sont des arbres binaires de recherche. De plus, tout comme dans le cas plaxique, le monoïde sylvestre est un tremplin pour la construction d’une algèbre qui généralise celle des fonctions symétriques [LR98], [HNT05]. Notons que sous certaines conditions, de tels monoïdes mènent à la construction de treillis. Par exemple, le monoïde sylvestre offre une construction très intéressante [HNT05] du treillis de Tamari [Tam62], [HT72]. L’objectif de ce chapitre est d’introduire et d’étudier un monoïde semblable au monoïde plaxique et au monoïde sylvestre, dont les classes d’équivalence sont en bijection avec les objets de la famille combinatoire de Baxter. La famille combinatoire de Baxter est constituée des classes combinatoires en bijection avec les permutations de Baxter [Bax64], qui sont des permutations qui évitent certains motifs. Citons par exemple les couples d’arbres binaires jumeaux [DG94], les quadrangulations [ABP04] et les orientations planes bipolaires [BBMF08], qui sont des objets de cette famille. Nous considérerons spécialement les couples d’arbres binaires jumeaux comme représentants de cette famille.

Bons monoïdes

Dans cette partie, avant de donner des exemples des monoïdes connus et qui sont à bien des rapports analogues au monoïde plaxique, nous rappelons la définition de ce qu’est un bon monoïde [Hiv04], à comprendre au sens « semblable au monoïde plaxique ». Nous terminons cette partie en présentant des opérations sur les bons monoïdes qui permettent d’en produire de nouveaux à partir d’anciens. 4.1.1 Définitions de base Définition 4.1.1. Une relation d’équivalence ≡ définie sur A∗ est une congruence de monoïde — ou simplement congruence si le contexte est clair — si pour tous mots u, u′ , v, v′ ∈ A∗ , u ≡ u ′ et v ≡ v ′ impliquent u · v ≡ u ′ · v ′ . (4.1.1) Une congruence ≡ permet de définir une structure de monoïde quotient du monoïde libre, que nous notons A∗/≡. En effet, si τ : A∗ → A∗/≡ est la projection canonique, l’ensemble A∗/≡ est muni du produit · défini, pour toutes classes d’équivalence xb et yb de A∗/≡, par xb · yb := τ (x · y), (4.1.2) où x et y sont des éléments quelconques de xb et de yb respectivement. Définition 4.1.2. Une relation d’équivalence ≡ définie sur A∗ est compatible avec la déstandardisation si pour tous mots u, v ∈ A∗ , u ≡ v si et seulement si std(u) ≡ std(v) et ev(u) = ev(v). (4.1.3) § 4.1 — Bons monoïdes 67 Lorsque ≡ est une congruence, nous dirons par extension que le monoïde A∗/≡ est compatible avec la déstandardisation si ≡ l’est. Cette définition signifie en particulier que tous les mots d’une classe d’équivalence d’une relation compatible avec la déstandardisation possèdent la même évaluation, et à plus forte raison, la même longueur. Remarquons ainsi que la classe d’équivalence d’une permutation est constituée uniquement de permutations. En plus de cela, ce type de relation d’équivalence possède l’attrait supplémentaire d’être plus simple à étudier. On peut en effet restreindre l’étude de la relation aux mots sans répétition de lettres. Définition 4.1.3. Une relation d’équivalence ≡ définie sur A∗ est compatible aux restrictions aux intervalles d’alphabet si pour tout intervalle I de A et tous mots u, v ∈ A∗ , u ≡ v implique u|I ≡ v|I . (4.1.4) Lorsque ≡ est une congruence, nous dirons par extension que le monoïde A∗/≡ est compatible avec la restriction aux intervalles d’alphabet si ≡ l’est. La définition suivante, due à Hivert [Hiv04], met en évidence une classe de congruences sur les mots, et ainsi du même coup une classe de monoïdes quotients du monoïde libre : Définition 4.1.4. Soit ≡ une relation d’équivalence sur A∗ . Si ≡ est une congruence de monoïde, compatible avec la déstandardisation et aux restrictions aux intervalles d’alphabet, alors, le monoïde quotient A∗/≡ est un bon monoïde. Il est remarquable que tous les bons monoïdes connus sont définis par l’intermédiaire d’un ensemble R de relations binaires sur A∗ . Une manière pratique de construire une congruence ≡ à partir d’un tel ensemble R consiste à considérer la relation binaire ←→ définie pour tout u, v ∈ A∗ par u ←→ v s’il existe y ∈ R tel que u y v ou v y u. (4.1.5) Deux mots sont déclarés équivalents s’ils sont en relation pour la congruence engendrée par la clôture réflexive et transitive de ←→. En d’autres termes, on pose xuy ≡ xu′y si u = u ′ ou s’il existe une suite de mots v (1), . . . , v(ℓ) tels que u ←→ v (1) ←→ · · · ←→ v (ℓ) ←→ u ′ . (4.1.6) Les relations de R sont appelées relations d’adjacence et peuvent dans certains cas être avantageusement vues comme des règles de réécriture — on pourra à ce sujet consulter [BN98]. Dans ce formalisme, deux mots sont équivalents si l’on peut réécrire l’un en l’autre par utilisation de la règle ←→. Dans ce qui suit, les congruences que nous allons considérer vont être définies en donnant simplement l’ensemble R des relations d’adjacence. Nous appelons alors la congruence ainsi obtenue à partir de R la congruence engendrée par R. Plusieurs questions peuvent se poser lorsque l’on étudie un bon monoïde A∗/≡. L’une des plus naturelles porte sur l’encodage de ses classes d’équivalence et d’algorithmes efficaces pour décider si deux mots sont équivalents. Une autre question est d’étudier le comportement de ≡ lorsque celle-ci est restreinte aux permutations, par exemple en comptant combien il y a de classes de permutations de taille n. De plus, il est également naturel d’observer si les classes de permutations forment un intervalle du permutoèdre, ou mieux, si la congruence de monoïde ≡ est aussi une congruence de ce treillis. 

Quelques exemples de bons monoïdes

Nous donnons dans cette partie quelques exemples et propriétés de base de quelques bons monoïdes connus. Le monoïde plaxique Le monoïde plaxique [LS81], [Lot02] est le quotient de A∗ par la congruence ≡P engendrée par les relations d’adjacence P1 ←−→ et P2 ←−→ définies pour a, b, c ∈ A par acb P1 ←−→ cab où a 6 b < c, (4.1.8) bac P2 ←−→ bca où a < b 6 c. (4.1.9) On vérifie sans peine que le monoïde plaxique est un bon monoïde. Il est de plus compatible avec l’involution de Schützenberger puisque l’image de la relation P1 ←−→ par l’involution de Schützenberger est P2 ←−→ et réciproquement. Les classes plaxiques de permutations sont en bijection avec les tableaux de Young standard [LS81], [Ful97]. Cette bijection se montre en effet par l’intermédiaire de la correspondance de Robinson-Schensted. Ainsi, les premiers cardinaux des classes plaxiques de permutations par taille sont 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, (4.1.10) et comptent également le nombre d’involutions sur [n] (suite A000085 de [Slo]). Le monoïde hypoplaxique Le monoïde hypoplaxique est le quotient de A∗ par la congruence ≡H engendrée par les relations d’adjacence H1 ←−→ et H2 ←−→ définies pour u ∈ A∗ et a, b, c ∈ A par ac u b H1 ←−→ ca u b où a 6 b < c, (4.1.11) b u ac H2 ←−→ b u ca où a < b 6 c. (4.1.12) Ce bon monoïde a été introduit par Krob et Thibon [KT97], [KT99] et étudié par Novelli [Nov98]. L’appellation « hypoplaxique » provient du fait qu’il forme un quotient du monoïde plaxique. En effet, pour tous mots u et v, si u ≡P v alors u ≡H v. Il est intéressant de noter que les classes de permutations sont en bijection avec les mots binaires, i.e., les mots sur l’alphabet {0, 1}. En effet, pour encoder une classe hypoplaxique de mots de taille n, il est nécessaire et suffisant d’encoder l’ensemble des reculs qui caractérisent cette classe. Toute classe hypoplaxique de permutations contient en effet toutes les permutations qui ont un ensemble de reculs donnés. Cet ensemble peut se représenter par le mot binaire b de longueur n − 1 où bi = 1 si et seulement si i est un recul des éléments de la classe encodée.