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} }$.