Associaèdre

En dimension 1, l'associaèdre K₃ 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₄ 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₅ est un ennéaèdre à neuf faces et quatorze sommets. Son dual est le prisme triangulaire triaugmenté.

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[4] 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[5].

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₃. 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₄ 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 à ${\displaystyle n}$ feuilles; elle produit directement les coordonnées entières des sommets dans l'espace à ${\displaystyle n-2}$ dimensions. La ${\displaystyle i}$-ème coordonnée de la réalisation de Loday est ${\displaystyle a_{i}b_{i}}$, où ${\displaystyle a_{i}}$ est le nombre de feuilles du sous-arbre gauche du ${\displaystyle i}$-ème nœud interne (numérotés de gauche à droite) et ${\displaystyle b_{i}}$ est le nombre de feuilles dans le sous-arbre droit[6]. On peut expliquer cette construction aussi sur les parenthésages de l'expression. Prenons, en suivant Casselman 2013, l'expression parenthésée ${\displaystyle e=(x_{0}(x_{1}x_{2}))(x_{3}x_{4})}$. Les sous-expressions sont

${\displaystyle 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 ${\displaystyle x_{0}(x_{1}x_{2})}$, la sous-expression de droite commence par ${\displaystyle x_{1}}$, donc l'indice de l'expression tout entière est 1. On note ${\displaystyle a_{i}}$ et ${\displaystyle b_{i}}$ le nombre de symboles dans la sous-expression gauche resp. droite de ${\displaystyle e_{i}}$. On obtient

${\displaystyle (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 ${\displaystyle a_{i}}$ et ${\displaystyle b_{i}}$; ici, le sommet de l'expression ${\displaystyle e}$ a pour coordonnées ${\displaystyle (2,1,6,1)}$.

On peut aussi réaliser l’associaèdre directement dans l'espace de dimension ${\displaystyle n-2}$ comme un polytope dont les normales aux faces ont les coordonnées dans ${\displaystyle 0,1}$, ou ${\displaystyle -1}$. Il existe a un nombre essentiellement exponentiel de façons de le faire[5] - [7]

   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[8].

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

• (en) Bryan Jacobs, « Associahedron », sur MathWorld
• (en) Bill Casselman, « Strange Associations », Feature Column, American Mathematical Society, 2013 (consulté le 30 novembre 2013)

• DocCourse Combinatorics and Geometry 2009. Notes d'un cours de Günter Ziegler à l'université autonome de Barcelone, 2009.