Permutoassociahedron
In mathematics, the permutoassociahedron is an formula_1-dimensional polytope whose vertices correspond to the bracketings of the permutations of formula_2 terms and whose edges connect two bracketings that can be obtained from one another either by moving a pair of brackets using associativity or by transposing two consecutive terms that are not separated by a bracket. The permutoassociahedron was first defined as a CW complex by Mikhail Kapranov who noted that this structure appears implicitly in Mac Lane's coherence theorem for symmetric and braided categories as well as in Vladimir Drinfeld's work on the Knizhnik–Zamolodchikov equations . It was constructed as a convex polytope by Victor Reiner and Günter M. Ziegler. Examples. When formula_3, the vertices of the permutoassociahedron can be represented by bracketing all the permutations of three terms formula_4, formula_5, and formula_6. There are six such permutations, formula_7, formula_8, formula_9, formula_10, formula_11, and formula_12, and each of them admits two bracketings (obtained from one another by associativity). For instance, formula_7 can be bracketed as formula_14 or as formula_15. Hence, the formula_16-dimensional permutoassociahedron is the dodecagon with vertices formula_15, formula_18, formula_19, formula_20, formula_21, formula_22, formula_23, formula_24, formula_25, formula_26, formula_27, and formula_14. When formula_29, the vertex  formula_30 is adjacent to exactly three other vertices of the permutoassociahedron: formula_31, formula_32, and formula_33. The first two vertices are reached from formula_30 via associativity and the third via a transposition. The vertex formula_31 is adjacent to four vertices. Two of them, formula_30 and formula_37, are reached via associativity, and the other two, formula_38 and formula_39, via a transposition. This illustrates that, in dimension formula_40 and above, the permutoassociahedron is not a simple polytope. Properties. The formula_1-dimensional permutoassociahedron has vertices. This is the product between the number of permutations of formula_2 terms and the number of all possible bracketings  of any such permutation. The former number is equal to the factorial formula_44 and the later is the formula_1th Catalan number. By its description in terms of bracketed permutations, the 1-skeleton of the permutoassociahedron is a flip graph with two different kinds of flips (associativity and transpositions).