Treillis de Tamari

Treillis de Tamari d'ordre 4. Le plus grand élément est a(b(c(de))), et le plus petit (((ab)c)d)e. Le treillis comporte 14 éléments.

En mathématiques discrètes, et notamment en combinatoire, un treillis de Tamari, introduit par le mathématicien Dov Tamari, est un ensemble partiellement ordonné dont les éléments sont les différentes façons de grouper une suite d'objets en paires par parenthésage ; par exemple, pour la suite abcd de quatre objets, il y a cinq groupements possibles, qui sont : ((ab)c)d, (ab)(cd), (a(bc))d, a((bc)d), et a(b(cd)).

Description

Chaque groupement décrit une façon de combiner les objets par une opération binaire, ou aussi l'ordre dans lequel on évalue les opérations; dans un treillis de Tamari, les divers groupements sont ordonnés : un groupement précède un autre si le deuxième s'obtient à partir du premier par l'application de la règle d'associativité (xy)z → x(yz) qui repousse les parenthèses vers la droite. Par exemple, on obtient (a(bc))d → a((bc)d), et dans le treillis de Tamari, on a (a(bc))d ≤ a((bc)d).

Propriétés

Pour l'ordre ainsi introduit, deux éléments $x$ et $y$ possèdent toujours une borne inférieure $x\wedge y$, et une borne supérieure $x\vee y$. Ainsi, le treillis de Tamari est bien un treillis au sens des ensembles ordonnés. Le plus grand élément est celui où les parenthésages se font le plus à gauche, et plus petit celui où les parenthésages sont le plus à droite. Le diagramme de Hasse de ce treillis est isomorphe au graphe d'un associaèdre. Le nombre d'éléments d'un treillis de Tamari pour une séquence de $n$ objets est le $n$Modèle:Exp nombre de Catalan.

Définitions équivalentes

Le treillis de Tamari peut être décrit de plusieurs autres manières, toutes plus ou moins liées aux diverses interprétations des nombres de Catalan eux-mêmes :

• C'est l'ensemble des suites d'entiers $(a_1,\dots ,a_n)$ tels que $i\le a_i\le n$ et, de plus, si $i\le j\le a_i$, alors $a_j\le a_i$Modèle:Harv.
• C'est l'ensemble des arbres binaires, avec l'opération de rotation.
• C'est aussi l'ensemble des forêts ordonnées. Une forêt est inférieure à une autre si le $j$Modèle:Exp nœud, dans un parcours préfixe de la première forêt a au moins autant de descendants que le $j$Modèle:Exp nœud de la deuxième forêt (caractérisation citée dans : Modèle:Harvsp).
• C'est l'ensemble des triangulations d'un polygone convexe à n sommets, ordonnées par l'opération flip qui consiste à enlever une arête de la triangulation, et de la remplacer, dans le quadrilatère apparaissant, par la diagonale opposée (ceci résulte de la dualité entre arbres binaires et triangulations).
• C'est aussi l'ensemble des chemins de Dyck de longueur $2n$, résultant du parcours des arbres binaires. L'ordre est induit par une rotation qui consiste à échanger un pas descendant avec le chemin de Dyck élémentaire (sans retour à 0) suivant.

Distance de rotation

La distance entre deux éléments d'un treillis de Tamari, vu comme un graphe, est la longueur de la plus courte chaîne qui relie ces éléments. Lorsque l'on considère les sommets du treillis comme des arbres binaires, cette distance est le nombre minimum de rotations qu'il faut faire pour passer du premier arbre au second. C'est pourquoi ce nombre est appelée distance de rotation. Le diamètre du treillis est la plus grande des distances de rotation dans le treillis. En 1988, Daniel Sleator, Robert Tarjan et William Thurston montrent que le diamètre des treillis de Tamari n'est jamais plus grand que 2n-6 quand n est supérieur à 9. Ils montrent également que cette borne supérieure est atteinte quand n est suffisamment grand. Ils conjecturent alors que, dans cette phrase, « suffisamment grand » signifie « supérieur à 9 ». Cette conjecture a été résolue en 2012 par Lionel Pournin.

Notes et références

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage
• Modèle:Article
• Modèle:Chapitre
• Modèle:Article
• Modèle:Article.
• Modèle:Ouvrage.

Articles liés

• Associaèdre
• Majorisation
• Treillis (ensemble ordonné)