# Associaèdre

En mathématiques, et notamment en combinatoire algébrique, un associaèdre est une réalisation géométrique d'un treillis de Tamari. L'associaèdre K$_n$ est un polytope (polyèdre convexe et borné) de dimension n-2 dans lequel chaque sommet correspond à une façon d'insérer des parenthèses ouvrantes et fermantes dans un mot de n lettres, et les arêtes correspondent à une application de la règle d'associativité. De manière équivalente, les sommets d'un associaèdre correspondent aux triangulations d'un polygone régulier à n+1 côtés et les arêtes correspondent à l’opération d'échange d'arêtes de la triangulation (flip en anglais), opération qui consiste à enlever une diagonale de la triangulation et à la remplacer par la diagonale opposée dans le quadrilatère qui apparaît. Enfin, la dualité entre arbres binaires et triangulations fait correspondre, aux sommets de l’associaèdre, les arbres binaires à n-1 nœuds, et les arêtes aux rotations dans les arbres.
Les associaèdres sont également appelés polytopes de Stasheff, d'après Jim Stasheff qui les a redécouverts au début des années 1960, dix ans après Tamari.
En 1988, Daniel Sleator, Robert Tarjan et William Thurston montrent que le diamètre des associaèdres n'est jamais plus grand que 2n-4 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.

## Exemples

En dimension 1, l'associaèdre K$_3$ représente les deux parenthésages ((xy)z) et (x(yz)) sur trois symboles, ou les deux triangulations d'un carré. C'est un segment de droite.
Dans le plan, l'associaèdre K$_4$ représente les cinq parenthésages sur quatre symboles, ou les cinq triangulations d'un pentagone régulier. C'est lui-même un pentagone.
Dans l'espace à trois dimensions, l'associaèdre K$_5$ est un ennéaèdre à neuf faces et quatorze sommets. Son dual est le prisme triangulaire triaugmenté.

## Réalisations

Initialement, Jim Stasheff considérait ces objets comme des polytopes en coordonnées curvilignes. L'introduction de l'article de Ceballos, Santos et Ziegler 2013 décrit les évolutions vers les réalisations actuelles.
Une des méthodes de réalisation de l'associaèdre est comme polytope secondaire d'un polygone régulier. Ce polytope a pour squelette le graphe des flip des triangulations (ou des rotations d'arbres binaires). Dans le graphe, chaque sommet représente un triangulation et deux sommets sont connectés si les trangulations si elles diffèrent par un flip.
Dans cette construction, chaque triangulation d'un polygone régulier à n+1 côtés correspond à un point de l'espace euclidien de dimension n+1; la i-ème coordonnée est la somme des aires des triangles incident au i-ème sommet du polygone. Par exemple, les deux triangulations du carré unité donnent deux points en dimension 4 de coordonnées respectivement (1,1/2,1,1/2) et (1/2,1,1/2,1). L'enveloppe convexe de ces points es la réalisation de l’associaèdre K$_3$. Même s'il est dans l'espace à 4 dimensions, c'est un segment de droite (un polytope de dimension 1) de cet espace. De manière similaire, l’associaèdre K$_4$ peut être réalisé de cette façon comme un pentagone de l'espace euclidien de dimension 5, dont les coordonnées sont obtenues par permutation circulaire du vecteur (1, 2+φ, 1, 1 + φ, 1 + φ) où φ dénote le nombre d'or. Toutefois cette réalisation conduit en général dès l'ordre 4 à des coordonnées qui sont des nombres irrationnels.
Une autre réalisation, due à Loday 2004, est basée sur la correspondance entre les sommets de l'associaèdre et les arbres binaires enracinés à $n$ feuilles; elle produit directement les coordonnées entières des sommets dans l'espace à $n-2$ dimensions. La $i$-ème coordonnée de la réalisation de Loday est $a_{i}b_{i}$, où $a_{i}$ est le nombre de feuilles du sous-arbre gauche du $i$-ème nœud interne (numérotés de gauche à droite) et $b_{i}$ est le nombre de feuilles dans le sous-arbre droit. On peut expliquer cette construction aussi sur les parenthésages de l'expression. Prenons, en suivant Casselman 2013, l'expression parenthésée $e=(x_{0}(x_{1}x_{2}))(x_{3}x_{4})$. Les sous-expressions sont
    $e_{1}=x_{0}(x_{1}x_{2}),e_{2}=x_{1}x_{2},e_{3}=(x_{0}(x_{1}x_{2}))(x_{3}x_{4}),e_{4}=x_{3}x_{4}$.
L'indice de la sous-expression est l'indice du symbole de gauche dans sa sous-expression droite : par exemple, dans $x_{0}(x_{1}x_{2})$, la sous-expression de droite commence par $x_{1}$, donc l'indice de l'expression tout entière est 1. On note $a_{i}$ et $b_{i}$ le nombre de symboles dans la sous-expression gauche resp. droite de $e_{i}$. On obtient
    $(a_{1},b_{1})=(1,2),(a_{2},b_{2})=(1,1),(a_{3},b_{3})=(3,2),(a_{4},b_{4})=(1,1)$.
Les coordonnées du sommet associé à l'expression est le produit des $a_{i}$ et $b_{i}$; ici, le sommet de l'expression $e$ a pour coordonnées $(2,1,6,1)$.
On peut aussi réaliser l’associaèdre directement dans l'espace de dimension $n-2$ comme un polytope dont les normales aux faces ont les coordonnées dans $0,1$, ou $-1$. Il existe a un nombre essentiellement exponentiel de façons de le faire$^,$

## Nombre de faces

* k = 1 2 3 4 5
* n
* 1 1 1
* 2 1 2 3
* 3 1 5 5 11
* 4 1 9 21 14 45
* 5 1 14 56 84 42 197
Le nombre de faces de dimension n − k de l'associaèdre K$_{n+1}$ est donné par le triangle numérique ci-contre. C'est la suite  A033282.
Le nombre de sommets de K$_{n+1}$ (sur la diagonale) est le n-ième nombre de Catalan. La deuxième colonne donne le nombre de faces dans K$_{n+1}$ (pour n ≥ 2). C'est le n-ième nombre triangulaire diminué de 1. La raison en est que chaque face correspond un sous-ensemble à 2 éléments d'un ensemble à n éléments, dont les groupements forment le treillis de Tamari T$_n$, à l'exception de la paire formée par le premier et le dernier élément.
Le nombre total de faces de toute dimensions (y compris l'associaèdre lui-même, mais sans l’ensemble vide) est donné par la dernière colonne du tableau représentant la somme des lignes. C'est le nombre de Schröder-Hipparque.

## Articles liés

* Cycloèdre (en), un polytope où la définition permet aux parenthèses de continuer en ordre cyclique.
* Permutoèdre, un polytope défini pour la commutativité, analogue à l'associaèdre définie pour l’associativité.
* Treillis de Tamari, le treillis dont le graphe est le squelette de l’associaèdre.