order polynomial

{{Distinguish|Order of a polynomial (disambiguation){{!}}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 $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 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)$ .{{cite book|last1=Stanley|first1=Richard P.|title=Ordered structures and partitions|date=1972|publisher=American Mathematical Society|location=Providence, Rhode Island}}

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:{{cite journal |last1=Stanley |first1=Richard P. |title=A chromatic-like polynomial for ordered sets |date=1970 |journal=Proc. Second Chapel Hill Conference on Combinatorial Mathematics and Its Appl. |pages=421–427}}

: $\Omega^\circ(n) = (-1)^$

\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.{{Cite book|title=Enumerative combinatorics. Volume 1|last1=Stanley | first1=Richard P.|date=2012|publisher=Cambridge University Press|isbn=9781139206549|edition=2nd|location=New York|chapter=4.5.14 Reciprocity theorem for linear homogeneous diophantine equations|oclc=777400915}}

Connections with other counting polynomials

=Chromatic polynomial =

The 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 \rightarrow 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) \rightarrow [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.{{cite journal|last1=Stanley|first1=Richard P.|title=Acyclic orientations of graphs|journal=Discrete Mathematics|date=1973|volume=5|issue=2|pages=171–178|doi=10.1016/0012-365X(73)90108-8|doi-access=}}

= Order polytope and Ehrhart polynomial =

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\mathbb{R}\mid 0\leq t\leq 1\}$ is the ordered unit interval, a continuous chain poset.{{cite journal |first1=Alexander |last1=Karzanov |first2=Leonid |last2=Khachiyan |title=On the conductance of Order Markov Chains |journal=Order |volume=8 |pages=7–15 |year=1991 |doi=10.1007/BF00385809|doi-access=|s2cid=120532896 }}{{cite journal |first1=Graham |last1=Brightwell |first2=Peter |last2=Winkler |title=Counting linear extensions |journal=Order |volume=8 |pages=225–242 |year=1991 |issue=3 |doi=10.1007/BF00383444|doi-access=|s2cid=119697949 }} More geometrically, we may list the elements $P=\{x_1,\ldots,x_p\}$ , and identify any mapping $f:P\to\mathbb R$ with the point $(f(x_1),\ldots,f(x_p))\in \mathbb{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$ .{{Cite journal|last=Stanley|first=Richard P.|date=1986|title=Two poset polytopes|journal=Discrete & Computational Geometry|volume=1|pages=9–23|doi=10.1007/BF02187680|doi-access=free}}

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

: $L(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.{{Cite book|title=Computing the continuous discretely|title-link= Computing the Continuous Discretely |last1=Beck|first1=Matthias|last2=Robins|first2=Sinai|publisher=Springer|year=2015|isbn=978-1-4939-2968-9|location=New York|pages=64–72}}

In fact, the Ehrhart polynomial of an order polytope is equal to the order polynomial of the original poset (with a shifted argument):{{cite journal|last=Linial|first=Nathan|year=1984|title=The information-theoretic bound is good for merging|journal=SIAM J. Comput.|volume=13|issue=4|pages=795–801|doi=10.1137/0213049}}
{{cite journal

| last1 = Kahn | first1 = Jeff

| last2 = Kim | first2 = Jeong Han

| doi = 10.1006/jcss.1995.1077

| issue = 3

| journal = Journal of Computer and System Sciences

| pages = 390–399

| title = Entropy and sorting.

| volume = 51

| year = 1995| doi-access = free

}}