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^[1].

En 1988, Daniel Sleator, Robert Tarjan et William Thurston^[2] 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^[3].

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.

• Cesar Ceballos, Francisco Santos et Günter M. Ziegler, « Many non-equivalent realizations of the associahedron », Arxiv,‎ 2013 (arXiv 1109.5544, lire en ligne).
• Frédéric Chapoton, « Sur le nombre d'intervalles dans les treillis de Tamari », Séminaire Lotharingien de Combinatoire, vol. 55,‎ 2006, article n^o B55f (MR 2264942, arXiv math/0602368, lire en ligne).
• Edward Early, « Chain lengths in the Tamari lattice », Annals of Combinatorics, vol. 8, n^o 1,‎ 2004, p. 37–43 (DOI 10.1007/s00026-004-0203-9, MR 2061375).
• Haya Friedman et Dov Tamari, « Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative », Journal of Combinatorial Theory, vol. 2, n^o 3,‎ 1967, p. 215–242 (DOI 10.1016/S0021-9800(67)80024-3, MR 0238984).
• Winfried Geyer, « On Tamari lattices », Discrete Mathematics, vol. 133, n^os 1–3,‎ 1994, p. 99–122 (DOI 10.1016/0012-365X(94)90019-1, MR 1298967).
• Christophe Hohlweg et Carsten E. M. C. Lange, « Realizations of the associahedron and cyclohedron », Discrete & Computational Geometry, vol. 37, n^o 4,‎ 2007, p. 517–543 (DOI 10.1007/s00454-007-1319-6, MR 2321739, arXiv math.CO/0510614).
• Ralf Holtkamp, « On Hopf algebra structures over free operads », Advances in Mathematics, vol. 207, n^o 2,‎ 2006, p. 544–565 (DOI 10.1016/j.aim.2005.12.004, MR 2271016, arXiv math/0407074).
• Samuel Huang et Dov Tamari, « Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law », Journal of Combinatorial Theory, Series A, vol. 13,‎ 1972, p. 7–13 (DOI 10.1016/0097-3165(72)90003-9, MR 0306064).
• Donald E. Knuth, The Art of Computer Programming, vol. IV : Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, 883 p. (ISBN 978-0-201-03804-0, présentation en ligne).
• Jean-Louis Loday, « Realization of the Stasheff polytope », Archiv der Mathematik, vol. 83, n^o 3,‎ 2004, p. 267–278 (DOI 10.1007/s00013-004-1026-y, MR 2108555).
• Lionel Pournin, « The diameter of associahedra », Advances in Mathematics, vol. 259,‎ 2014, p. 13–42 (DOI 10.1016/j.aim.2014.02.035, arXiv 1207.6296).
• Lionel Pournin, « A combinatorial method to find sharp lower bounds on flip distances », dans FPSAC'13 : 25th International Conference on Formal Power Series and Algebraic Combinatorics, DMTCS Proceedings, 2013 (lire en ligne), p. 1-11
• Daniel Sleator, Robert Tarjan et William Thurston, « Rotation distance, triangulations, and hyperbolic geometry », J. Amer. Math. Soc., vol. 1,‎ 1988, p. 647–681
• James Dillon Stasheff, « Homotopy associativity of H-spaces. I, II », Transactions of the American Mathematical Society, vol. 108,‎ 1963, p. 293–312 (MR 0158400) (Version révisée de sa thèse de 1961, Princeton University lien Math Reviews).
• Dov Tamari, « The algebra of bracketings and their enumeration », Nieuw Archief voor Wiskunde, Ser. 3, vol. 10,‎ 1962, p. 131–146 (MR 0146227).
• Dov Tamari, « Monoïdes préordonnés et chaînes de Malcev », Thèse, Université de Paris,‎ 1951 (MR 0051833).
• Dov Tamari, « Monoïdes préordonnés et chaînes de Malcev », Bulletin de la Société Mathématique de France, vol. 82,‎ 1954, p. 53-96 (MR 16,110a, zbMATH 0055.01501, lire en ligne) (Texte issu de la thèse de l’auteur, de même titre, soutenue en 1951).
• Folkert Müller-Hoissen, Jean Marcel Pallo et Jim Stasheff (éditeurs), Associahedra, Tamari lattices and related structures : Tamari memorial Festschrift, Birkhäuser/Springer Verlag, coll. « Progress in Mathematics » (n^o 229), 2012.

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

• Portail des mathématiques