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.

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

The number of such maps is the strict order polynomial

The order-preserving maps generalize the linear extensions of

In fact, the leading coefficient of

is the number of linear extensions divided by

There is only one linear extension (the identity mapping), and both polynomials have leading term

linear extensions, and both polynomials reduce to the leading term

There is a relation between strictly order-preserving maps and order-preserving maps:[3] In the case that

is a chain, this recovers the negative binomial identity.

There are similar results for the chromatic polynomial and Ehrhart polynomial (see below), all special cases of Stanley's general Reciprocity Theorem.

counts the number of proper colorings of a finite graph

, there is a natural "downstream" partial order on the vertices

(Thus, the Hasse diagram of the poset is a subgraph of the oriented graph

runs over all acyclic orientations of G, considered as poset structures.

elements, the order polytope

is the set of order-preserving maps

is the ordered unit interval, a continuous chain poset.

[6][7] More geometrically, we may list the elements

; then the order polytope is the set of points

[2] The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope.

; then we define the number of lattice points in

by a positive integer scalar

Ehrhart showed that this is a rational polynomial of degree

In fact, the Ehrhart polynomial of an order polytope is equal to the order polynomial of the original poset (with a shifted argument):[2][9]

This is an immediate consequence of the definitions, considering the embedding of the