Permutation polytopes corresponding to strongly supermodular functions

Abstract

Throughout, let p be a positive integer and let Sigma be the set of permutations over {1,....p}. A real-valued function lambda over subsets of {1,... p}, with lambda(theta)=0, defines a mapping of Sigma into R-p where delta is an element of Sigma is mapped into the vector lambda(delta) whose kth coordinate (lambda(delta))(k) is the augmented-value obtained from adding k to the coordinates that precede it, according to the ranking induced by sigma. 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. (C) 2003 Elsevier B.V. All rights reserved.