Treillis de m-Tamari

Les treillis m-Tamari sur les arbres

Définition sur les chemins

Définition 8.1.1. Un m-ballot path de taille n est un chemin dans le plan depuis l’origine (0, 0) jusqu’au point (nm, n) formé de pas « montants » verticaux (0, 1) et de pas « descendants » horizontaux (1, 0) tel que le chemin reste toujours au dessus de la droite y = x m . Tout comme les chemins de Dyck, les m-ballot paths peuvent s’interpréter comme des mots sur un alphabet binaire {1, 0} où les pas montants sont codés par la lettre 1 et les pas descendants par 0. De même, un chemin est dit primitif s’il n’a pas d’autres contacts avec la droite y = x m que ses extrémités. La rotation est alors définie comme dans la définition 6.1.2 et illustrée figure 8.2. −→ 10100 0 110100000 100 −→ 10100 110100000 0 100 Figure 8.2 – Rotations sur les m-ballot paths. 164 Chapitre 8 — Treillis de m-Tamari Si on considère la rotation sur les chemins comme une relation de couverture, l’ordre induit est un treillis qui généralise l’ordre de Tamari usuel [BPR12]. En exemple, on donne l’ordre sur les 2-ballot paths de taille 3, T (2) 3 figure 8.1. En remplaçant chaque pas montant par une suite de m pas montants, on peut faire correspondre injectivement un chemin de Dyck de taille m.n à chaque mballot path. L’ensemble obtenu est composé de chemins de Dyck dont les cardinaux des suites de pas montants sont divisibles par m. On appelle ces objets les chemins de m-Dyck. Un exemple de la correspondance est donnée figure 8.3.

Arbres m + 1-aires

Les arbres m-binaires ont une structure m+ 1-aire : on peut donc leur associer un arbre m + 1-aire. Si T est un arbre m-binaire non vide, T est composé de TL, TR1 , . . . , TRm, on lui associe l’arbre T˜ dont les sous-arbres sont dans cet ordre T˜ L, T˜ R1 , . . . , T˜ Rm. Un exemple est donné en figure 8.9. La bijection entre les chemins de Dyck et les arbres binaires donne le passage d’un chemin de m-Dyck à un arbre m-binaire et donc par extension d’un m-ballot paths à un arbre m + 1-aire. Les m-ballot paths admettent aussi une structure 168 Chapitre 8 — Treillis de m-Tamari Figure 8.8 – Treillis de m-Tamari T (2) 3 sur les arbres ternaires m + 1-aire. Un m-ballot path D s’exprime récursivement comme D = DL 1 DRm 0 DRm−1 . . . 0 DR1 0 (8.7) et cette structure reflète exactement celle de l’arbre correspondant, comme on peut le voir dans la figure 8.9. Cette bijection permet de représenter l’ordre de m-Tamari sur les arbres m+1- aires, ce que nous avons fait dans les figures 8.10 et 8.8. La relation de couverture se comprend à partir des arbres m-binaires. A partir d’un arbre m-binaire, deux types de rotations sont possibles : entre la racine de l’arbre TL et la racine de T, et entre un nœud racine de T et le nœud le plus à gauche d’un arbre TRi . Ces deux rotations donnent deux types de transformations sur les arbres m + 1-aires : passage de la branche gauche à une des branches droites et passage d’une branche droite à une autre. On donne le schéma général de ces deux opérations sur les arbres m-binaires et leur traduction en terme d’arbres m + 1-aires dans figures 8.11 et 8.12.