Equivalence of permutation polytopes corresponding to strictly supermodular functions
A \(p\)-set function is a real-valued function \(\lambda\) defined on the subsets of \(\{1,2,\dots,p\}\) with \(\lambda(\emptyset)=0\). A \(p\)-set function is called strictly supermodular if for every \(I,J\subset\{1,2,\dots,p\}\) we have \(\lambda(I\cup J)+\lambda(I\cap J)\geq \lambda(I)+\lambda(J)\) with the strict inequality whenever \(I\not\subseteq J\) and \(J\not\subseteq I\). Given a permutation \(\sigma\) of \(\{1,2,\dots,p\}\) and \(t\in \{1,2,\dots,p\}\), let \(I_\sigma(t)\) be the integers preceding \(t\) according to \(\sigma\). Moreover, each permutation \(\sigma\) defines a vector \(\lambda_\sigma\in{\mathbb R}^p\) with \((\lambda)_k=\lambda[\{k\}\cup I_\sigma(k)(k)]-\lambda[I_\sigma(k)]\). The permutation polytope corresponding to \(\lambda\) is the convex hull of the vectors \(\lambda_\sigma\) with \(\sigma\) ranging over all permutations of \(\{1,2\dots,p\}\). The main results of the paper demonstrate that face-lattices of all permutation polytopes are isomorphic and that the sets of tangential hulls of their faces coincide.
- Cores of convex games
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 848091 (Why is no real title available?)
- scientific article; zbMATH DE number 876684 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Lectures on Polytopes
- Partition polytopes over 1-dimensional points
- Permutation polytopes corresponding to strongly supermodular functions
- Structure of a simple scheduling polyhedron
- Submodular functions and optimization
- The Partial Order of a Polymatroid Extreme Point
- Theory of capacities
This page was built for publication: Equivalence of permutation polytopes corresponding to strictly supermodular functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q947118)
