Associaèdre

thumb|K5 est le diagramme de Hasse du treillis de Tamari T4. thumb|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. 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. 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. 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.