Order 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}${\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.

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

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

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

${\displaystyle \Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)}${\displaystyle \Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)} and ${\displaystyle \Omega ^{\circ }(n)={\binom {n}{p}}.}${\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}}${\displaystyle {\tfrac {1}{p!}}n^{p}}.

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

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

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

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

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

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

where ${\displaystyle \sigma }${\displaystyle \sigma } runs over all acyclic orientations of G, considered as poset structures.^[5]

The order polytope associates a polytope with a partial order. For a poset ${\displaystyle P}${\displaystyle P} with ${\displaystyle p}${\displaystyle p} elements, the order polytope ${\displaystyle O(P)}${\displaystyle O(P)} is the set of order-preserving maps ${\displaystyle f:P\to [0,1]}${\displaystyle f:P\to [0,1]}, where ${\displaystyle [0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}${\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}\}}${\displaystyle P=\{x_{1},\ldots ,x_{p}\}}, and identify any mapping ${\displaystyle f:P\to \mathbb {R} }${\displaystyle f:P\to \mathbb {R} } with the point ${\displaystyle (f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}}${\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}}${\displaystyle (t_{1},\ldots ,t_{p})\in [0,1]^{p}} with ${\displaystyle t_{i}\leq t_{j}}${\displaystyle t_{i}\leq t_{j}} if ${\displaystyle x_{i}\leq x_{j}}${\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}}${\displaystyle L=\mathbb {Z} ^{n}} and a ${\displaystyle d}${\displaystyle d}-dimensional polytope ${\displaystyle K\subset \mathbb {R} ^{d}}${\displaystyle K\subset \mathbb {R} ^{d}} with vertices in ${\displaystyle L}${\displaystyle L}; then we define

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

the number of lattice points in ${\displaystyle nK}${\displaystyle nK}, the dilation of ${\displaystyle K}${\displaystyle K} by a positive integer scalar ${\displaystyle n}${\displaystyle n}. Ehrhart showed that this is a rational polynomial of degree ${\displaystyle d}${\displaystyle d} in the variable ${\displaystyle n}${\displaystyle n}, provided ${\displaystyle K}${\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).}${\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)}${\displaystyle (n{+}1)}-chain poset ${\displaystyle [n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R} }${\displaystyle [n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R} }.

• Order theory
• Polynomials
• Polytopes