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

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:[2]

\Omega ^{\circ }(n)=(-1)^{|P|}\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.[3]

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.[4]

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

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

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

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

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

References

Stanley, Richard P. (1972). Ordered structures and partitions. Providence, Rhode Island: American Mathematical Society.
Stanley, Richard P. (1970). "A chromatic-like polynomial for ordered sets". Proc. Second Chapel Hill Conference on Combinatorial Mathematics and Its Appl.: 421–427.
Stanley, Richard P., 1944- (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.CS1 maint: multiple names: authors list (link)
Stanley, Richard P. (1973). "Acyclic orientations of graphs". Discrete Math. 5 (2): 171–178. doi:10.1016/0012-365X(73)90108-8.
Karzanov, Alexander; Khachiyan, Leonid (1991). "On the conductance of Order Markov Chains". Order. 8: 7–15. doi:10.1007/BF00385809. S2CID 120532896.
Brightwell, Graham; Winkler, Peter (1991). "Counting linear extensions". Order. 8 (3): 225–242. doi:10.1007/BF00383444. S2CID 119697949.
Stanley, Richard P. (1986). "Two poset polytopes". Discrete Comput. Geom. 1: 9–23. doi:10.1007/BF02187680.
Beck, Matthias; Robins, Sinai (2015). Computing the continuous discretely. New York: Springer. pp. 64–72. ISBN 978-1-4939-2968-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: 390–399. doi:10.1145/129712.129731. ISBN 0897915119.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Stanley, Richard P. (1972). Ordered structures and partitions. Providence, Rhode Island: American Mathematical Society.

[2] Stanley, Richard P. (1970). "A chromatic-like polynomial for ordered sets". Proc. Second Chapel Hill Conference on Combinatorial Mathematics and Its Appl.: 421–427.

[3] Stanley, Richard P., 1944- (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.CS1 maint: multiple names: authors list (link)

[4] Stanley, Richard P. (1973). "Acyclic orientations of graphs". Discrete Math. 5 (2): 171–178. doi:10.1016/0012-365X(73)90108-8.

[5] Karzanov, Alexander; Khachiyan, Leonid (1991). "On the conductance of Order Markov Chains". Order. 8: 7–15. doi:10.1007/BF00385809. S2CID 120532896.

[6] Brightwell, Graham; Winkler, Peter (1991). "Counting linear extensions". Order. 8 (3): 225–242. doi:10.1007/BF00383444. S2CID 119697949.

[Stanley1986-7] Stanley, Richard P. (1986). "Two poset polytopes". Discrete Comput. Geom. 1: 9–23. doi:10.1007/BF02187680.

[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: 390–399. doi:10.1145/129712.129731. ISBN 0897915119.