In mathematics, the order polytope of a finite

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

is a

convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

defined from the set. The points of the order polytope are the

monotonic function In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...

s from the given set to the

unit interval In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis, ...

, its vertices correspond to the

upper set In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...

s 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

as the

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

indicator vector In mathematics, the indicator vector or characteristic vector or incidence vector of a subset ''T'' of a Set (mathematics), set ''S'' is the vector x_T := (x_s)_ such that x_s = 1 if s \in T and x_s = 0 if s \notin T. If ''S'' is countable set, cou ...

s of the sets of edges of

n

-vertex transitive tournaments.

Definition and example

is a pair

(S,\le)

where

S

is an arbitrary set and

\le

is a

binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...

on pairs of elements of

S

that is reflexive (for all

x\in S

x\le x

), antisymmetric (for all

x,y\in S

with

x\ne y

at most one of

x\le y

and

y\le x

can be true), and transitive (for all

x,y,z\in S

, if

x\le y

and

y\le z

then

x\le z

). A partially ordered set

(S,\le)

is said to be finite when

S

is a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...

. In this case, the collection of all functions

f

that map

S

to the

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...

s forms a finite-dimensional

vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...

, with

pointwise addition In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined ...

of functions as the vector sum operation. The dimension of the space is just the number of elements of

S

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

f

with the following two properties: * For every

x\in S

0\le f(x)\le 1

. That is,

f

maps the elements of

S

to the

. * For every

x,y\in S

with

x\le y

f(x)\le f(y)

. That is,

f

is a

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

x

and

y

, with

x \le y

in the partial order, the functions

f

from these points to real numbers can be identified with points

(f(x),f(y))

in the

Cartesian plane A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in t ...

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

(x,y)

-plane with

0\le x\le y \le 1

. This is an

isosceles right triangle A special right triangle is a right triangle with some regular feature that makes calculations on the triangle easier, or for which simple formulas exist. For example, a right triangle may have angles that form simple relationships, such as 45° ...

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

\

. That is, the order polytope is an

integral polytope In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are a ...

; it has no vertices with fractional coordinates. These functions are exactly the

indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...

s of

s of the partial order. Therefore, the number of vertices equals the number of upper sets. The

facets A facet is a flat surface of a geometric shape, e.g., of a cut gemstone. Facet may also refer to: Arts, entertainment, and media * ''Facets'' (album), an album by Jim Croce * ''Facets'', a 1980 album by jazz pianist Monty Alexander and his tri ...

of the order polytope are of three types: *Inequalities

0\le f(x)

for each minimal element

x

of the partially ordered set, *Inequalities

f(y)\le 1

for each maximal element

y

of the partially ordered set, and *Inequalities

f(x)\le f(y)

for each two distinct elements

x,y

that do not have a third distinct element

z

between them; that is, for each pair

(x,y)

in the

covering relation In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically expres ...

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

f

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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...

is a special type of

simplex In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...

called an order simplex or orthoscheme. Each point of the

unit cube A unit cube, more formally a cube of side 1, is a cube whose sides are 1 unit long.. See in particulap. 671. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units.. Unit hypercube The term '' ...

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 Congruence may refer to: Mathematics * Congruence (geometry), being the same size and shape * Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure * In mod ...

to each other and (for orders on

n

elements) there are

n!

different linear orders, the

volume Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). The de ...

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 In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extens ...

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 In mathematics, an integral polytope has an associated Ehrhart polynomial that encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a highe ...

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

x

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

x

. For the order polytope, the Ehrhart polynomial equals (after a minor change of variables) the

order polynomial The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a poset to a chain of length n. These order-pres ...

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

Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...

for finite

distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...

s, the

s 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

p

and

q

both belong to the order polytope of a partially ordered set

(S,\le)

, then the function

p\wedge q

that maps

x

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

, and the function

p\vee q

that maps

x

\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

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

References

{{reflist, refs= {{citation , last = Birkhoff , first = Garrett , authorlink = Garrett Birkhoff , doi = 10.1215/S0012-7094-37-00334-X , issue = 3 , journal = Duke Mathematical Journal , pages = 443–454 , title = Rings of sets , volume = 3 , year = 1937 {{citation , last1 = Brightwell , first1 = Graham , author1-link = Graham Brightwell , last2 = Winkler , first2 = Peter , author2-link = Peter Winkler , doi = 10.1007/BF00383444 , issue = 3 , journal = Order , mr = 1154926 , pages = 225–242 , title = Counting linear extensions , volume = 8 , year = 1991, s2cid = 119697949 {{citation , last1 = Felsner , first1 = Stefan , last2 = Knauer , first2 = Kolja , doi = 10.1016/j.ejc.2010.07.011 , issue = 1 , journal = European Journal of Combinatorics , mr = 2727459 , pages = 45–59 , title = Distributive lattices, polyhedra, and generalized flows , volume = 32 , year = 2011, doi-access = free . See in particular Remark 11, p. 53. {{citation , last1 = Grötschel , first1 = Martin , author1-link = Martin Grötschel , last2 = Jünger , first2 = Michael , last3 = Reinelt , first3 = Gerhard , doi = 10.1007/BF01582010 , issue = 1 , journal =

Mathematical Programming Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, mr = 809748 , pages = 43–60 , title = Facets of the linear ordering polytope , volume = 33 , year = 1985, s2cid = 21071064 {{citation , last = Stanley , first = Richard , author-link = Richard P. Stanley , pages = 571–572, 645 , title = Enumerative Combinatorics, Volume 1, second edition, version of 15 July 2011 , url = https://www-math.mit.edu/~rstan/ec/ec1.pdf , year = 2011 {{citation , last = Stanley , first = Richard P. , doi = 10.1007/BF02187680 , issue = 1 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geom ...

, mr = 824105 , pages = 9–23 , title = Two poset polytopes , volume = 1 , year = 1986, doi-access = free Order theory Polytopes