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. These order-preserving maps were first introduced by Richard P. Stanley while studying ordered structures and partitions as a Ph.D. student at Harvard University in 1971 under the guidance of Gian-Carlo Rota.

Definition

Let be a finite poset with elements denoted, and let be a chain elements. A map is order-preserving if implies. The number of such maps grows polynomially with, and the function that counts their number is the order polynomial.
Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps, meaning implies. The number of such maps is the strict order polynomial .
Both and have degree. The order-preserving maps generalize the linear extensions of, the order-preserving bijections. In fact, the leading coefficient of and is the number of linear extensions divided by.

Examples

Letting be a chain of elements, we have
and
There is only one linear extension, and both polynomials have leading term.
Letting be an antichain of incomparable elements, we have. Since any bijection is order-preserving, there are linear extensions, and both polynomials reduce to the leading term.

Reciprocity theorem

There is a relation between strictly order-preserving maps and order-preserving maps:
In the case that is a chain, this recovers the negative binomial identity. There are similar results for the chromatic polynomial and Ehrhart polynomial, all special cases of Stanley's general Reciprocity Theorem.

Connections with other counting polynomials

Chromatic polynomial

The chromatic polynomial counts the number of proper colorings of a finite graph with available colors. For an acyclic orientation of the edges of, there is a natural "downstream" partial order on the vertices implied by the basic relations whenever is a directed edge of. We say is compatible with if is order-preserving. Then we have
where runs over all acyclic orientations of G, considered as poset structures.

Order polytope and Ehrhart polynomial

The order polytope associates a polytope with a partial order. For a poset with elements, the order polytope is the set of order-preserving maps, where is the ordered unit interval, a continuous chain poset. More geometrically, we may list the elements, and identify any mapping with the point ; then the order polytope is the set of points with if.
The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope. Specifically, consider the lattice and a -dimensional polytope with vertices in ; then we define
the number of lattice points in, the dilation of by a positive integer scalar. Ehrhart showed that this is a rational polynomial of degree in the variable, provided has vertices in the lattice.
In fact, the Ehrhart polynomial of an order polytope is equal to the order polynomial of the original poset :
This is an immediate consequence of the definitions, considering the embedding of the -chain poset.