In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the upper sets of the partial order, and its dimension is the number of elements in the partial order. The order polytope is a distributive polytope, meaning that coordinatewise minima and maxima of pairs of its points remain within the polytope. The order polytope of a partial order should be distinguished from the linear ordering polytope, a polytope defined from a number n {\displaystyle n} as the convex hull of indicator vectors of the sets of edges of n {\displaystyle n} -vertex transitive tournaments.
Definition and example A partially ordered set is a pair ( S , ≤ ) {\displaystyle (S,\leq )} where S {\displaystyle S} is an arbitrary set and ≤ {\displaystyle \leq } is a binary relation on pairs of elements of S {\displaystyle S} that is reflexive (for all x ∈ S {\displaystyle x\in S} , x ≤ x {\displaystyle x\leq x} ), antisymmetric (for all x , y ∈ S {\displaystyle x,y\in S} with x ≠ y {\displaystyle x\neq y} at most one of x ≤ y {\displaystyle x\leq y} and y ≤ x {\displaystyle y\leq x} can be true), and transitive (for all x , y , z ∈ S {\displaystyle x,y,z\in S} , if x ≤ y {\displaystyle x\leq y} and y ≤ z {\displaystyle y\leq z} then x ≤ z {\displaystyle x\leq z} ). A partially ordered set ( S , ≤ ) {\displaystyle (S,\leq )} is said to be finite when S {\displaystyle S} is a finite set. In this case, the collection of all functions f {\displaystyle f} that map S {\displaystyle S} to the real numbers forms a finite-dimensional vector space, with pointwise addition of functions as the vector sum operation. The dimension of the space is just the number of elements of S {\displaystyle S} . The order polytope is defined to be the subset of this space consisting of functions f {\displaystyle f} with the following two properties:
For every x ∈ S {\displaystyle x\in S} , 0 ≤ f ( x ) ≤ 1 {\displaystyle 0\leq f(x)\leq 1} . That is, f {\displaystyle f} maps the elements of S {\displaystyle S} to the unit interval. For every x , y ∈ S {\displaystyle x,y\in S} with x ≤ y {\displaystyle x\leq y} , f ( x ) ≤ f ( y ) {\displaystyle f(x)\leq f(y)} . That is, f {\displaystyle f} is a monotonic function For example, for a partially ordered set consisting of two elements x {\displaystyle x} and y {\displaystyle y} , with x ≤ y {\displaystyle x\leq y} in the partial order, the functions f {\displaystyle f} from these points to real numbers can be identified with points ( f ( x ) , f ( y ) ) {\displaystyle (f(x),f(y))} in the Cartesian plane. For this example, the order polytope consists of all points in the ( x , y ) {\displaystyle (x,y)} -plane with 0 ≤ x ≤ y ≤ 1 {\displaystyle 0\leq x\leq y\leq 1} . This is an isosceles right triangle with vertices at (0,0), (0,1), and (1,1).
Vertices and facets The vertices of the order polytope consist of monotonic functions from S {\displaystyle S} to { 0 , 1 } {\displaystyle \{0,1\}} . That is, the order polytope is an integral polytope; it has no vertices with fractional coordinates. These functions are exactly the indicator functions of upper sets of the partial order. Therefore, the number of vertices equals the number of upper sets. The facets of the order polytope are of three types:
… excerpt ends here. Continue reading the full article.
