Order polynomial explained

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

P be a finite poset with p elements denoted x,y \in P , and let [n] = \{ 1 < 2 <\ldots<n\} be a chain n elements. A map \phi: P \to [n] is order-preserving if x \leq y implies \phi(x) \leq \phi(y) . The number of such maps grows polynomially with n , and the function that counts their number is the order polynomial \Omega(n) = \Omega(P,n) .

Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps

\phi: P \to [n] , meaning x < y implies \phi(x) < \phi(y) . The number of such maps is the strict order polynomial \Omega ^{\circ} (n) = \Omega ^{\circ} (P,n) .^[1]

Both

\Omega(n) and \Omega ^{\circ(n)} have degree p . The order-preserving maps generalize the linear extensions of P , the order-preserving bijections \phi:P\stackrel{\sim}{\longrightarrow}[p] . In fact, the leading coefficient of \Omega(n) and \Omega ^{\circ(n)} is the number of linear extensions divided by p! .

Examples

Letting

P be a chain of p elements, we have

\Omega(n) = \binom{n + p -1 }{p} = \left(\left({n\atop p}\right)\right) and \Omega ^{\circ(n)} = \binom{n}{p}.

There is only one linear extension (the identity mapping), and both polynomials have leading term \tfrac 1 {p!}n ^{p} .

Letting

P be an antichain of p incomparable elements, we have \Omega(n) = \Omega ^{\circ(n)} = n ^{p} . Since any bijection \phi:P\stackrel{\sim}{\longrightarrow}[p] is (strictly) order-preserving, there are p! linear extensions, and both polynomials reduce to the leading term \tfrac {p!}{p!}n ^{p} = n ^{p} .

Reciprocity theorem

There is a relation between strictly order-preserving maps and order-preserving maps:^[2]

\Omega ^{\circ(n)} = ( -1 ) ^{|P|} \Omega( - n).

In the case that

P 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.^[3]

Connections with other counting polynomials

Chromatic polynomial

P(G,n) counts the number of proper colorings of a finite graph G with n available colors. For an acyclic orientation \sigma of the edges of G , there is a natural "downstream" partial order on the vertices V(G) implied by the basic relations u > v whenever u → v is a directed edge of \sigma . (Thus, the Hasse diagram of the poset is a subgraph of the oriented graph \sigma .) We say \phi: V(G) → [n] is compatible with \sigma if \phi is order-preserving. Then we have P(G,n) = \sum _{\sigma} \Omega ^{\circ(\sigma,n),}

where

\sigma runs over all acyclic orientations of G, considered as poset structures.^[4]

Order polytope and Ehrhart polynomial

See main article: Order polytope. The order polytope associates a polytope with a partial order. For a poset

P with p elements, the order polytope O(P) is the set of order-preserving maps f:P\to [ 0 , 1 ] , where [ 0 , 1 ] = \{ t\in R \mid 0 \leq t\leq 1 \} is the ordered unit interval, a continuous chain poset.^{[5] [6]} More geometrically, we may list the elements P = \{x _{1,\ldots,x} _{p\}} , and identify any mapping f:P\to R with the point (f(x _{1),\ldots,f(x} _{p))\in} R ^{p} ; then the order polytope is the set of points (t _{1,\ldots,t} _{p)\in} [ 0 , 1 ] ^{p} with t _{i} \leq t _{j} if x _{i} \leq x _{j} .^[7]

The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope. Specifically, consider the lattice

L = Z ^{n} and a d -dimensional polytope K\subset R ^{d} with vertices in L ; then we defineL(K,n) = \#(nK \cap L),

the number of lattice points in

nK , the dilation of K by a positive integer scalar n . Ehrhart showed that this is a rational polynomial of degree d in the variable n , provided K has vertices in the lattice.^[8]

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

L(O(P),n) = \Omega(P,n{ + } 1 ).

This is an immediate consequence of the definitions, considering the embedding of the (n{ + } 1 ) -chain poset [n{ + } 1 ] = \{ 0 < 1 < … <n\}\subset R .

Notes and References

1. Book: Stanley. Richard P.. Ordered structures and partitions. 1972. American Mathematical Society. Providence, Rhode Island.
2. Stanley . Richard P. . A chromatic-like polynomial for ordered sets . 1970 . Proc. Second Chapel Hill Conference on Combinatorial Mathematics and Its Appl. . 421 - 427.
3. Book: Enumerative combinatorics. Volume 1. Stanley . Richard P.. 2012. Cambridge University Press. 9781139206549. 2nd. New York. 4.5.14 Reciprocity theorem for linear homogeneous diophantine equations. 777400915.
4. Stanley. Richard P.. Acyclic orientations of graphs. Discrete Mathematics. 1973. 5. 2. 171–178. 10.1016/0012-365X(73)90108-8.
5. Alexander . Karzanov . Leonid . Khachiyan . On the conductance of Order Markov Chains . . 8 . 7 - 15 . 1991 . 10.1007/BF00385809. 120532896 .
6. Graham . Brightwell . Peter . Winkler . Counting linear extensions . . 8 . 225 - 242 . 1991 . 3 . 10.1007/BF00383444. 119697949 .
7. Stanley. Richard P.. 1986. Two poset polytopes. Discrete & Computational Geometry. 1. 9–23. 10.1007/BF02187680. free.
8. Book: Computing the continuous discretely. Computing the Continuous Discretely . Beck. Matthias. Robins. Sinai. Springer. 2015. 978-1-4939-2968-9. New York. 64–72.
9. Linial. Nathan. 1984. The information-theoretic bound is good for merging. SIAM J. Comput.. 13. 4. 795 - 801. 10.1137/0213049.
   Kahn . Jeff . Kim . Jeong Han . 10.1006/jcss.1995.1077 . 3 . Journal of Computer and System Sciences . 390–399 . Entropy and sorting. . 51 . 1995. free .