Order polytope explained

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

as the convex hull of indicator vectors of the sets of edges of

-vertex transitive tournaments.

Definition and example

A partially ordered set is a pair

(S,\le)

where

is an arbitrary set and

\le

is a binary relation on pairs of elements of

that is reflexive (for all

x\inS

x\lex

), antisymmetric (for all

x,y\inS

with

x\ney

at most one of

x\ley

and

y\lex

can be true), and transitive (for all

x,y,z\inS

, if

x\ley

and

y\lez

then

x\lez

A partially ordered set

(S,\le)

is said to be finite when

is a finite set. In this case, the collection of all functions

that map

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

. The order polytope is defined to be the subset of this space consisting of functions

with the following two properties:

For every

x\inS

0\lef(x)\le1

. That is,

maps the elements of

to the unit interval.

For every

x,y\inS

with

x\ley

f(x)\lef(y)

. That is,

is a monotonic function

For example, for a partially ordered set consisting of two elements

and

, with

x\ley

in the partial order, the functions

from these points to real numbers can be identified with points

(f(x),f(y))

in the Cartesian plane. For this example, the order polytope consists of all points in the

(x,y)

-plane with

0\lex\ley\le1

. 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

\{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:

Inequalities

0\lef(x)

for each minimal element

of the partially ordered set,

Inequalities

f(y)\le1

for each maximal element

of the partially ordered set, and

Inequalities

f(x)\lef(y)

for each two distinct elements

x,y

that do not have a third distinct element

between them; that is, for each pair

(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

\bot

below all elements in the partial order and

\top

above all elements, mapped by

to 0 and 1 respectively,and keeping only inequalities of the third type for the resulting augmented partially ordered set.

More generally, with the same augmentation by

\bot

and

\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.

Volume and Ehrhart polynomial

The order polytope of a linear order is a special type of simplex called an order simplex or orthoscheme. Each point of the unit cube whose coordinates are all distinct lies in a unique one of these orthoschemes, the order simplex for the linear order of its coordinates.Because these order simplices are all congruent to each other and (for orders on

elements) there are

different linear orders, the volume of each order simplex is

1/n!

. More generally, an order polytope can be partitioned into order simplices in a canonical way, with one simplex for each linear extension of the corresponding partially ordered set.Therefore, the volume of any order polytope is

1/n!

multiplied by the number of linear extensions of the corresponding partially ordered set. This connection between the number of linear extensions and volume can be used to approximate the number of linear extensions of any partial order efficiently (despite the fact that computing this number exactly is

P-complete

) by applying a randomized polynomial-time approximation scheme for polytope volume.

The Ehrhart polynomial of the order polytope is a polynomial whose values at integer values

give the number of integer points in a copy of the polytope scaled by a factor of

. For the order polytope, the Ehrhart polynomial equals (after a minor change of variables) the order polynomial of the corresponding partially ordered set. This polynomial encodes several pieces of information about the polytope including its volume (the leading coefficient of the polynomial and its number of vertices (the sum of coefficients).

Continuous lattice

By Birkhoff's representation theorem for finite distributive lattices, the upper sets of any partially ordered set form a finite distributive lattice, and every finite distributive lattice can be represented in this way. The upper sets correspond to the vertices of the order polytope, so the mapping from upper sets to vertices provides a geometric representation of any finite distributive lattice. Under this representation, the edges of the polytope connect comparable elements of the lattice.

If two functions

and

both belong to the order polytope of a partially ordered set

(S,\le)

, then the function

p\wedgeq

that maps

min(p(x),q(x))

,and the function

p\veeq

that maps

max(p(x),q(x))

both also belong to the order polytope.The two operations

\wedge

and

\vee

give the order polytope the structure of a continuous distributive lattice, within which the finite distributive lattice of Birkhoff's theorem is embedded.That is, every order polytope is a distributive polytope. The distributive polytopes with all vertex coordinates equal to 0 or 1 are exactly the order polytopes