Order polynomial

Not to be confused with Order of a 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 ${\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 [n]=\{1<2<\ldots <n\}}$ be a chain ${\displaystyle n}$ elements. A map ${\displaystyle \phi :P\to [n]}$ 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 [n]}$, 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)}$. ^[1]

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 }}[p]}$. In fact, the leading coefficient of ${\displaystyle \Omega (n)}$ and ${\displaystyle \Omega ^{\circ }\!(n)}$ is the number of linear extensions divided by ${\displaystyle p!}$. ^[2]

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 }}[p]}$ 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: ^[3]

${\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. ^[4]

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 [n]}$ 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. ^[5]

Order polytope and Ehrhart polynomial

Main article: Order polytope

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 [0,1]}$, where ${\displaystyle [0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}$ is the ordered unit interval, a continuous chain poset. ^{[6] [7]} 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 [0,1]^{p}}$ with ${\displaystyle t_{i}\leq t_{j}}$ if ${\displaystyle x_{i}\leq x_{j}}$. ^[2]

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

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

${\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 [n{+}1]=\{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 .