The shuffle pasting (Q596650)

This article develops the theory of loop-free pasting schemes. A pasting scheme generalises a directed graph in the same way as an incidence complex or geometry generalises a graph. The article starts by considering some unresolved problems in the (relatively new) theory of pasting schemes. In particular, the article explains the difficulties that arise when one attempts to build a well-structured loop-free pasting scheme from a combinatorial object called the permutohedron. The \(n\)-permutohedron \(P_n\) is a combinatorial object constructed from the set \(S_n\) of all permutations on \(\{1,\dots,n\}\). So far, no method has been found ``to endow \(P_n\) with the structure of [a] well-formed loop-free pasting scheme''. After illustrating the difficulties that arise, the author considers a similar combinatorial object constructed from a subset namely, the set of all \((p,q)\)-shuffles. One definition of a \((p,q)\)-shuffle is that it is a permutation \(\sigma\) which is increasing on \(\{1,\dots,p\}\) and \(\{p+1,\dots,p+q=n\}\). From the combinatorial object he shows how to construct a well-formed loop-free pasting scheme, and suggests that the results obtained may be useful as a step towards a solution of the unsolved problems.