Permutation polytopes corresponding to strongly supermodular functions Original Research Article

Throughout, let p be a positive integer and let Σ be the set of permutations over {1,…,p}. A real-valued function λ over subsets of {1,…,p}, with λ(∅)=0, defines a mapping of Σ into Rp where σ∈Σ is mapped into the vector λσ whose kth coordinate (λσ)k is the augmented λ-value obtained from adding k to the coordinates that precede it, according to the ranking induced by σ. The permutation polytope corresponding to λ is then the convex hull of the vectors corresponding to all permutations. We introduce a new class of strongly supermodular functions and for such functions we derive an isomorphic representation for the face-lattices of the corresponding permutation polytope.