Jump to content

Order polynomial

From Wikipedia, the free encyclopedia

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

[edit]

Let be a finite poset with elements denoted , and let be a chain elements. A map is order-preserving if implies . The number of such maps grows polynomially with , and the function that counts their number is the order polynomial .

Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps , meaning implies . The number of such maps is the strict order polynomial .[1]

Both and have degree . The order-preserving maps generalize the linear extensions of , the order-preserving bijections . In fact, the leading coefficient of and is the number of linear extensions divided by .[2]

Examples

[edit]

Letting be a chain of elements, we have

and

There is only one linear extension (the identity mapping), and both polynomials have leading term .

Letting be an antichain of incomparable elements, we have . Since any bijection is (strictly) order-preserving, there are linear extensions, and both polynomials reduce to the leading term .

Reciprocity theorem

[edit]

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

In the case that 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

[edit]

Chromatic polynomial

[edit]

The chromatic polynomial counts the number of proper colorings of a finite graph with available colors. For an acyclic orientation of the edges of , there is a natural "downstream" partial order on the vertices implied by the basic relations whenever is a directed edge of . (Thus, the Hasse diagram of the poset is a subgraph of the oriented graph .) We say is compatible with if is order-preserving. Then we have

where runs over all acyclic orientations of G, considered as poset structures.[5]

Order polytope and Ehrhart polynomial

[edit]

The order polytope associates a polytope with a partial order. For a poset with elements, the order polytope is the set of order-preserving maps , where is the ordered unit interval, a continuous chain poset.[6][7] More geometrically, we may list the elements , and identify any mapping with the point ; then the order polytope is the set of points with if .[2]

The Ehrhart polynomial counts the number of integer lattice points inside the dilations of a polytope. Specifically, consider the lattice and a -dimensional polytope with vertices in ; then we define

the number of lattice points in , the dilation of by a positive integer scalar . Ehrhart showed that this is a rational polynomial of degree in the variable , provided 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]

This is an immediate consequence of the definitions, considering the embedding of the -chain poset .

References

[edit]
  1. ^ Stanley, Richard P. (1972). Ordered structures and partitions. Providence, Rhode Island: American Mathematical Society.
  2. ^ a b c 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.