Decomposing Sets of Inversions

Lukas Katthän

Abstract


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.

Keywords


Inversion sets; Permutation graphs; Simple Permutations; Linear Ordering Polytope

Full Text: PDF