Associaèdre

une réalisation géométrique d'un treillis de Tamari

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

Le polytope de Stasheff K5
K5 est le diagramme de Hasse du treillis de Tamari T4.
Les 9 faces de K5.
Chaque sommet du diagramme de Hasse possède les ovales des trois faces adjacente. Les faces dont les ovales s'intersectent ne se touchent pas.

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

modifier

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

Réalisations

modifier

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 K3. 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 K4 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 à   feuilles; elle produit directement les coordonnées entières des sommets dans l'espace à   dimensions. La  -ème coordonnée de la réalisation de Loday est  , où   est le nombre de feuilles du sous-arbre gauche du  -ème nœud interne (numérotés de gauche à droite) et   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  . Les sous-expressions sont

 .

L'indice de la sous-expression est l'indice du symbole de gauche dans sa sous-expression droite : par exemple, dans  , la sous-expression de droite commence par  , donc l'indice de l'expression tout entière est 1. On note   et   le nombre de symboles dans la sous-expression gauche resp. droite de  . On obtient

 .

Les coordonnées du sommet associé à l'expression est le produit des   et  ; ici, le sommet de l'expression   a pour coordonnées  .

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

Nombre de faces

modifier
   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 nk de l'associaèdre Kn+1 est donné par le triangle numérique ci-contre. C'est la suite  A033282.

Le nombre de sommets de Kn+1 (sur la diagonale) est le n-ième nombre de Catalan. La deuxième colonne donne le nombre de faces dans Kn+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 Tn, à 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

modifier

Notes et références

modifier
  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.
  5. a et b Ceballos, Santos et Ziegler 2013.
  6. Loday 2004.
  7. Hohlweg et Lange 2007.
  8. 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

modifier

Liens externes

modifier