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