Misplaced Pages

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

Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps ${\displaystyle \phi :P\to }$, meaning ${\displaystyle x<y}$ implies ${\displaystyle \phi (x)<\phi (y)}$. The number of such maps is the strict order polynomial ${\displaystyle \Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)}$.

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

Examples

Letting ${\displaystyle P}$ be a chain of ${\displaystyle p}$ elements, we have

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

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

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

Reciprocity theorem

There is a relation between strictly order-preserving maps and order-preserving maps:

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

In the case that ${\displaystyle 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.

Connections with other counting polynomials

Chromatic polynomial

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

${\displaystyle P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),}$

where ${\displaystyle \sigma }$ 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 ${\displaystyle P}$ with ${\displaystyle p}$ elements, the order polytope ${\displaystyle O(P)}$ is the set of order-preserving maps ${\displaystyle f:P\to }$, where ${\displaystyle =\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}$ is the ordered unit interval, a continuous chain poset. More geometrically, we may list the elements ${\displaystyle P=\{x_{1},\ldots ,x_{p}\}}$, and identify any mapping ${\displaystyle f:P\to \mathbb {R} }$ with the point ${\displaystyle (f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}}$; then the order polytope is the set of points ${\displaystyle (t_{1},\ldots ,t_{p})\in ^{p}}$ with ${\displaystyle t_{i}\leq t_{j}}$ if ${\displaystyle x_{i}\leq x_{j}}$.

The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope. Specifically, consider the lattice ${\displaystyle L=\mathbb {Z} ^{n}}$ and a ${\displaystyle d}$-dimensional polytope ${\displaystyle K\subset \mathbb {R} ^{d}}$ with vertices in ${\displaystyle L}$; then we define

${\displaystyle L(K,n)=\#(nK\cap L),}$

the number of lattice points in ${\displaystyle nK}$, the dilation of ${\displaystyle K}$ by a positive integer scalar ${\displaystyle n}$. Ehrhart showed that this is a rational polynomial of degree ${\displaystyle d}$ in the variable ${\displaystyle n}$, provided ${\displaystyle K}$ has vertices in the lattice.

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

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

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

References

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

• Order theory
• Polynomials
• Polytopes