Permutoassociahedron Explained

In mathematics, the permutoassociahedron is an

n -dimensional polytope whose vertices correspond to the bracketings of the permutations of n +1 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.^[1] It was constructed as a convex polytope by Victor Reiner and Günter M. Ziegler.^[2]

Examples

When

n = 2 , the vertices of the permutoassociahedron can be represented by bracketing all the permutations of three terms a , b , and c . There are six such permutations, abc , acb , bac , bca , cab , and cba , and each of them admits two bracketings (obtained from one another by associativity). For instance, abc can be bracketed as (ab)c or as a(bc) . Hence, the 2 -dimensional permutoassociahedron is the dodecagon with vertices a(bc) , a(cb) , (ac)b , (ca)b , c(ab) , c(ba) , (cb)a , (bc)a , b(ca) , b(ac) , (ba)c , and (ab)c .

When

n = 3 , the vertex ((ab)c)d is adjacent to exactly three other vertices of the permutoassociahedron: (ab)(cd) , (a(bc))d , and ((ba)c)d . The first two vertices are reached from ((ab)c)d via associativity and the third via a transposition. The vertex (ab)(cd) is adjacent to four vertices. Two of them, ((ab)c)d and a(b(cd)) , are reached via associativity, and the other two, (ba)(cd) and (ab)(dc) , via a transposition. This illustrates that, in dimension 3 and above, the permutoassociahedron is not a simple polytope.^[3]

Properties

The

n -dimensional permutoassociahedron hasn!{ 2 n\choose n} vertices. This is the product between the number of permutations of n +1 terms and the number of all possible bracketings of any such permutation. The former number is equal to the factorial (n +1 )! and the later is the n th 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).

See also

• Permutohedron
• Associahedron
• Cyclohedron

Notes and References

1. Mikhail M. . Kapranov . Mikhail Kapranov. The permutoassociahedron, Mac Lane's coherence theorem and asymptotic zones for the KZ equation. Journal of Pure and Applied Algebra. 85. 2. 1993. 119–142. 10.1016/0022-4049(93)90049-Y .
2. Reiner . Victor. Ziegler . Günter M. . Günter M. Ziegler. Coxeter-associahedra. Mathematika. 41. 2. 1994. 364–393. 10.1112/S0025579300007452.
3. Baralić . Djordje. Ivanović . Jelena. Petrić . Zoran. A simple permutoassociahedron. Discrete Mathematics. 342. 12. December 2019. 111591. 10.1016/j.disc.2019.07.007. 1708.02482.