Order polytope

A partially ordered set is a pair ${\displaystyle (S,\leq )}$ where ${\displaystyle S}$ is an arbitrary set and ${\displaystyle \leq }$ is a binary relation on pairs of elements of ${\displaystyle S}$ that is reflexive (for all ${\displaystyle x\in S}$, ${\displaystyle x\leq x}$), antisymmetric (for all ${\displaystyle x,y\in S}$ with ${\displaystyle x\neq y}$ at most one of ${\displaystyle x\leq y}$ and ${\displaystyle y\leq x}$ can be true), and transitive (for all ${\displaystyle x,y,z\in S}$, if ${\displaystyle x\leq y}$ and ${\displaystyle y\leq z}$ then ${\displaystyle x\leq z}$).

A partially ordered set ${\displaystyle (S,\leq )}$ is said to be finite when ${\displaystyle S}$ is a finite set. In this case, the collection of all functions ${\displaystyle f}$ that map ${\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 ${\displaystyle S}$. The order polytope is defined to be the subset of this space consisting of functions ${\displaystyle f}$ with the following two properties:^[2][3]

• For every ${\displaystyle x\in S}$, ${\displaystyle 0\leq f(x)\leq 1}$. That is, ${\displaystyle f}$ maps the elements of ${\displaystyle S}$ to the unit interval.
• For every ${\displaystyle x,y\in S}$ with ${\displaystyle x\leq y}$, ${\displaystyle f(x)\leq f(y)}$. That is, ${\displaystyle f}$ is a monotonic function

For example, for a partially ordered set consisting of two elements ${\displaystyle x}$ and ${\displaystyle y}$, with ${\displaystyle x\leq y}$ in the partial order, the functions ${\displaystyle f}$ from these points to real numbers can be identified with points ${\displaystyle (f(x),f(y))}$ in the Cartesian plane. For this example, the order polytope consists of all points in the ${\displaystyle (x,y)}$-plane with ${\displaystyle 0\leq x\leq y\leq 1}$. This is an isosceles right triangle with vertices at (0,0), (0,1), and (1,1).

The vertices of the order polytope consist of monotonic functions from ${\displaystyle S}$ to ${\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.^[2]

The facets of the order polytope are of three types:^[2]

• Inequalities ${\displaystyle 0\leq f(x)}$ for each minimal element ${\displaystyle x}$ of the partially ordered set,
• Inequalities ${\displaystyle f(y)\leq 1}$ for each maximal element ${\displaystyle y}$ of the partially ordered set, and
• Inequalities ${\displaystyle f(x)\leq f(y)}$ for each two distinct elements ${\displaystyle x,y}$ that do not have a third distinct element ${\displaystyle z}$ between them; that is, for each pair ${\displaystyle (x,y)}$ in the covering relation of the partially ordered set.

The facets can be considered in a more symmetric way by introducing special elements ${\displaystyle \bot }$ below all elements in the partial order and ${\displaystyle \top }$ above all elements, mapped by ${\displaystyle f}$ to 0 and 1 respectively, and keeping only inequalities of the third type for the resulting augmented partially ordered set.^[2]

More generally, with the same augmentation by ${\displaystyle \bot }$ and ${\displaystyle \top }$, the faces of all dimensions of the order polytope correspond 1-to-1 with quotients of the partial order. Each face is congruent to the order polytope of the corresponding quotient partial order.^[2]