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

Exemples

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

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^[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 à $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^[6]. 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^[5]^,^[7]

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

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.

Notes et références

Notes

↑ L'article de Stasheff 1963 est issu de sa thèse soutenue à Princeton en 1961. La thèse de Tamari 1954 qui date de 1951 a été publiée, mais sans la figure du polytope, dans le Bulletin de la Société mathématique de France. Stasheff relate les circonstances dans sa contribution (How I ‘met’ Dov Tamari) à la Festschrift (2012), p. 45-63.
↑ Sleator, Tarjan et Thurston 1988.
↑ Pournin 2014.
↑ Le squelette d'un polytope est le graphe formé de ses sommets et des arêtes reliant ces somets.
↑ ^{a et b} Ceballos, Santos et Ziegler 2013.
↑ Loday 2004.
↑ Hohlweg et Lange 2007.
↑ Holtkamp 2006.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Associahedron » (voir la liste des auteurs).

Bibliographie

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.

Liens externes

(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

[1] L'article de Stasheff 1963 est issu de sa thèse soutenue à Princeton en 1961. La thèse de Tamari 1954 qui date de 1951 a été publiée, mais sans la figure du polytope, dans le Bulletin de la Société mathématique de France. Stasheff relate les circonstances dans sa contribution (How I ‘met’ Dov Tamari) à la Festschrift (2012), p. 45-63.

[2] Sleator, Tarjan et Thurston 1988.

[3] Pournin 2014.

[4] Le squelette d'un polytope est le graphe formé de ses sommets et des arêtes reliant ces somets.

[csz-5] {a et b} Ceballos, Santos et Ziegler 2013.

[6] Loday 2004.

[7] Hohlweg et Lange 2007.

[8] Holtkamp 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]