Abstract
The permutahedron Perm(P) of a poset P is defined as the convex hull of those permutations that are linear extensions of P. Von Arnim et al. (1990) gave a linear description of the permutahedron of a series-parallel poset. Unfortunately, their main theorem characterizing the facet defining inequalities is only correct for not series-decomposable posets. We do not only give a proof of the revised version of this theorem but also extend it partially to the case of arbitrary posets and obtain a new complete and minimal description of Perm(P) if P is series-parallel. Furthermore, we summarize briefly results about the corresponding separation problem.
Original language | English |
---|---|
Pages (from-to) | 85-90 |
Number of pages | 6 |
Journal | Discrete Applied Mathematics |
Volume | 57 |
Issue number | 1 |
DOIs | |
State | Published - 10 Feb 1995 |
Externally published | Yes |