Decomposing Sets of Inversions

  • Lukas Katthän
Keywords: Inversion sets, Permutation graphs, Simple Permutations, Linear Ordering Polytope


In this paper we consider the question how the set of inversions of a permutation $\pi \in S_n$ can be partitioned into two subsets, which are themselves inversion sets of permutations in $S_n$. Our method is to study the modular decomposition of the inversion graph of $\pi$. A correspondence to the substitution decomposition of $\pi$ is also given. Moreover, we consider the special case of multiplicative decompositions.
Article Number