orderpolynomial

The order polynomial, usually denoted Omega(P; m) or Ω(P; m), is a polynomial associated with a finite partially ordered set (poset) P. It counts the number of order-preserving maps from P into a chain with m elements, typically the set {1, 2, ..., m} with the natural order. Equivalently, Omega(P; m) is the number of colorings of the elements of P with colors 1 through m that respect the poset order (if x ≤ y in P, then the color of x is not greater than the color of y).

As a function of m, Omega(P; m) is a polynomial of degree equal to the size of P. Its leading coefficient is 1, and all coefficients are nonnegative. The polynomial encodes the combinatorial structure of P and is closely related to the order polytope of P, a polytope whose lattice points correspond to order-preserving labelings. In particular, Omega(P; m) equals the number of lattice points in the dilate m·O(P), where O(P) is the order polytope of P; this connects Omega(P; m) to Ehrhart theory.

Two simple examples illustrate the concept. If P is an antichain on n elements, every labeling is order-preserving, so Omega(P; m) = m^n. If P is a chain of n elements, order-preserving labelings correspond to weak compositions of n into m parts, giving Omega(P; m) = binomial(m + n − 1, n).

There is a reciprocity theorem due to Stanley: Omega(P; −m) = (−1)^{|P|} Omega^*(P; m), where Omega^*(P; m) counts strictly order-preserving maps (f(x) < f(y) whenever x < y). The concept is a cornerstone of P-partitions and poset enumerations.