Associahedron

In mathematics, an associahedron Kn is an (n − 2)-dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a word of n letters and the edges correspond to single application of the associativity rule.

Description

Equivalently, the vertices of an associahedron correspond to the triangulations of a regular polygon with n + 1 sides and the edges correspond to edge flips in which a single diagonal is removed from a triangulation and replaced by a different diagonal.

Associahedra are also called Stasheff polytopes after the work of Jim Stasheff, who rediscovered them in the early 1960s after earlier work on them by Dov Tamari.

See also

• Associative property
• Cyclohedron, a polytope whose definition allows parentheses to wrap around in cyclic order.
• Flip graph - a generalization of the n-skeleton of the associahedron.
• Permutohedron, a polytope defined from commutativity in a similar way to the definition of the associahedron from associativity.
• Polytope
• Tamari lattice, a lattice whose graph is the skeleton of the associahedron.

External links

• Associahedron @ Wikipedia