Treillis de Tamari

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).

Pour l'ordre ainsi introduit, deux éléments ${\displaystyle x}$ et ${\displaystyle y}$ possèdent toujours une borne inférieure ${\displaystyle x\land y}$, et une borne supérieure ${\displaystyle x\lor 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 ${\displaystyle n}$ objets est le ${\displaystyle n}$^ième nombre de Catalan.

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 ${\displaystyle (a_{1},\ldots ,a_{n})}$ tels que ${\displaystyle i\leq a_{i}\leq n}$ et, de plus, si ${\displaystyle i\leq j\leq a_{i}}$, alors ${\displaystyle a_{j}\leq a_{i}}$(Huang et Tamari 1972).
• 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 ${\displaystyle j}$^ième nœud, dans un parcours préfixe de la première forêt a au moins autant de descendants que le ${\displaystyle j}$^ième nœud de la deuxième forêt (caractérisation citée dans : Knuth 2011, Section 7.2.1.6: Generating All Trees[1]).
• 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 ${\displaystyle 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.

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[2] 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[3].

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