A combinatorial study of partial order polytopes
The convex hull of the characteristic vectors of all partial orders on a finite set \(A\) of cardinality \(\geq 2\) is called partial order polytope of \(A\). The author studies the facial structure of partial order polytopes, and his main results are the following: Deciding whether or not two distinct vertices of a partial order polytope are non-adjacent is an NP-complete problem. And a convex polytope \(P\) is affinely equivalent to a face of some partial order polytope iff \(P\) is affinely equivalent to a face of some 3-SAT polytope.
facial structure of partial order polytopes
scientific article; zbMATH DE number 1891294
scientific article