A combinatorial study of partial order polytopes (Q1867280)

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.