“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

. 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

be a finite poset,

and

be points in

and

be a chain of length

. A map

is order-preserving if

implies

. The number of such maps grows polynomially with

, and the function that counts their number as a function of

is the order polynomial

Similarly, we can define an order polynomial that counts the number of strictly order-preserving maps. A map

is strictly order-preserving if

implies

. The order polynomial that counts the number of these maps is denoted by

.^[1]

Examples

We can also consider the poset

with

disjoint points. Then the number of order-preserving maps to a chain of length

, and

Reciprocity theorem

The reciprocity theorem shows that there is a relation between strictly order-preserving maps and order-preserving maps. In addition, this comes hand in hand with important properties that the chromatic polynomial and Ehrhart polynomial share. The relation can be stated as follows:^[2]

Connections

Chromatic polynomial

The chromatic polynomial counts the number of proper ways to color a graph. Let

be a finite graph and let

be an acyclic orientation of

. Then there is a natural binary relation on the vertices

defined as

. In particular,

is a partial ordering on the set of vertices

. In addition,

is compatible with

is order-preserving. Then, we can conclude that

Ehrhart polynomial

The Ehrhart polynomial is a polynomial that associates the number of integer lattice points and the expansion of a polytope

by a factor of

. In other words, consider the lattice

and a

-dimensional polytope in

with integer vertices. Let

be a positive integer, and

be a dilation of

is the number of lattice points in

. Eugène Ehrhart showed that this was a rational polynomial of degree

.^[4]

Order polytope

The order polytope associates a polytope with a partial order. Let

be a poset with

elements. Then the order polytope, denoted

, is the set of points in the

-dimensional unit cube such that the coordinates satisfy the partial order.^[5]^[6]

More formally, let

be the set of all functions from

. The order polytope

of the poset

is the set of all maps

which satisfy the following two conditions. First,

for all

, and second,

in the ordering of

. Thus, the polytope can be created given a poset and a partial order.^[7]

The volume of the order polytope is given by the leading coefficient of the order polynomial, which is the number of linear extensions of the poset

divided by

.^[7]^[8]

References

1. ^{{cite book|last1=Stanley|first1=Richard P.|title=Ordered structures and partitions|date=1972|publisher=American Mathematical Society|location=Providence, Rhode Island}}
2. ^{{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}}
3. ^{{cite journal|last1=Stanley|first1=Richard P.|title=Acyclic orientations of graphs|journal=Discrete Math|date=1973|volume=5|pages=171–178}}
4. ^{{Cite book |title=Computing the continuous discretely |last=Beck |first=Matthias |last2=Robins |first2=Sinai |publisher=Springer |year=2015 |isbn=978-1-4939-2968-9 |location=New York |pages=64–72}}
5. ^{{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}}
6. ^{{cite journal |first1=Graham |last1=Brightwell |first2=Peter |last2=Winkler |title=Counting linear extensions |journal=Order |volume=8 |pages=225–242 |year=1991 |doi=10.1007/BF00383444}}
7. ^¹{{Cite journal|last=Stanley|first=Richard P.|date=1986|title=Two poset polytopes|url=|journal=Discrete Comput. Geom.|doi=10.1007/BF02187680|pmid=|access-date=}}
8. ^{{cite journal|first=Nathan|last=Linial|year=1984|title=The information-theoretic bound is good for merging|journal=SIAM J. Comput.|volume=13|pages=795–801|doi=10.1137/0213049}}
{{cite journal|first1=Jeff|last1=Kahn| first2=Jeong Han|last2=Kim|title=Entropy and sorting|doi=10.1145/129712.129731|journal=Journal of Computer and System Sciences|volume=51|year=1995|pages=390–399}}