nLab order polynomial

Contents

Contents

Idea

The order polynomial Ω P(n)\Omega_P(n) of a finite partially ordered set PP counts the number of ways that PP can be extended to a linear order of size nn.

Definition

By a linear extension of PP of size nn, we mean an order-preserving function from PP to (n)={1<<n}(n) = \{ 1 \lt \cdots \lt n \}. To see that

Ω P(n)=|Hom(P,(n))|\Omega_P(n) = |Hom(P,(n))|

defines a polynomial in nn, first observe that any function P(n)P \to (n) factors as a surjection from PP onto some (k)={1<<k}(k) = \{ 1 \lt \cdots \lt k \} (where knk \le n), followed by an injection from (k)(k) to (n)(n). The total number of order-preserving functions from PP to (n)(n) can therefore be calculated explicitly as

Ω P(n)= k=1 |P|e k(nk)\Omega_P(n) = \sum_{k=1}^{|P|} e_k \binom{n}{k}

where e ke_k is the number of surjective order-preserving functions from PP to (k)(k). Hence Ω P(n)\Omega_P(n) is a polynomial of degree equal to the cardinality of PP.

Examples

The order polynomial of (3)={1<2<3}(3) = \{ 1 \lt 2 \lt 3 \} is

n+2(n2)+(n3)=n 3+3n 2+2n6n + 2 \binom{n}{2} + \binom{n}{3} = \frac{n^3 + 3n^2 + 2n}{6}

For example, evaluating the polynomial at n=3n=3 confirms that there are 10 order-preserving functions from (3)(3) to itself.

The order polynomial of the 3-element poset

P= c a bP = \array{&&c&& \\ &\nearrow& &\nwarrow& \\ a &&&& b}

is n+3(n2)+2(n3)=2n 3+3n 2+n6n + 3 \binom{n}{2} + 2\binom{n}{3} = \frac{2n^3 + 3n^2 + n}{6}. Evaluating at n=2n=2, we compute that there are 5 order-preserving functions from PP onto (2)(2).

Properties

Relation to zeta polynomial

Let P (2) PP^\downarrow \cong (2)^P denote the lattice of lower sets in PP. The order polynomial of a finite poset PP is related to the zeta polynomial of its lattice of lower sets P P^\downarrow by the equation1

Ω P(n+2)=Z P (n)\Omega_P(n+2) = Z_{P^\downarrow}(n)

This can be seen as a consequence of the currying isomorphisms

Hom([n],P )Hom([n]×P,(2))Hom(P,[n] )Hom([n], P^\downarrow) \cong Hom([n] \times P, (2)) \cong Hom(P, [n]^\downarrow)

together with the isomorphisms [n] [n+1](n+2)[n]^\downarrow \cong [n+1] \cong (n+2).

Relation to the strict order polynomial

Let Ω¯ P(n)\bar{\Omega}_P(n) denote the number of strict order-preserving functions from PP to (n)(n), that is, functions f:P(n)f : P \to (n) such that x<yx \lt y implies f(x)<f(y)f(x) \lt f(y). This again defines a polynomial in nn, called the strict order polynomial of PP. The strict order polynomial of a finite poset PP is related to its order polynomial by the equation

Ω¯ P(n)=(1) pΩ P(n)\bar{\Omega}_P(n) = (-1)^p \Omega_P(-n)

where p=|P|p = |P| is the cardinality of PP. This is an example of a combinatorial reciprocity theorem in the sense of Stanley (1974).

(Notice that we are evaluating the order polynomial at a negative integer, even though the putative definition Ω P(n)=|Hom(P,(n))|\Omega_P(n) = |Hom(P,(n))| only makes sense for natural numbers nn. This is justified because the value of a polynomial on the natural numbers determines its value on arbitrary integers.)

As an example, the strict order polynomial of the 3-element poset PP defined above is Ω¯ P(n)=2n 33n 2+n6\bar{\Omega}_P(n) = \frac{2n^3 - 3n^2 + n}{6}. Evaluation at n=2n=2 confirms that there is exactly one strict monotone map from PP to a 2-element linear order (sending both aa and bb to the first element and cc to the second element).

Through Möbius inversion, this equation relating the strict order polynomial to the order polynomial can be connected to the previous one relating the order polynomial to the zeta polynomial. Since the lattice of lower sets P P^\downarrow has bottom and top elements, we know that

Ω P(n)=Z P (n2)=ζ n(,P) \Omega_P(n) = Z_{P^\downarrow}(n-2) = \zeta^n(\emptyset,P)

where ζ n\zeta^n is the nn-fold convolution of the zeta function of P P^\downarrow. One can similarly work out that

Ω¯ P(n)=(1) pμ n(,P) \bar{\Omega}_P(n) = (-1)^p\mu^n(\emptyset,P)

where μ n\mu^n is the nn-fold convolution of the Möbius function of P P^\downarrow. The equation Ω¯ P(n)=(1) pΩ P(n)\bar{\Omega}_P(n) = (-1)^p \Omega_P(-n) then follows formally from the fact that μ=ζ 1\mu = \zeta^{-1}.

Computational complexity

Counting the number of total linear extensions of a poset (i.e., number of linear extensions of an nn-element poset to a linear order of size nn) is a #P-complete problem (Brightwell and Winkler 1991), and thus so is the problem of computing the leading coefficient of the order polynomial (cf. Browning, Hopkins, and Kelley 2017).

References

  • Richard P. Stanley. Ordered structures and partitions. Memoirs of the AMS 119, 1972. (doi) (Free copy available from the author’s website, see #9.)
  • Richard P. Stanley. Combinatorial Reciprocity Theorems. Advances in Mathematics 14:194-253, 1974. (Free copy available from the author’s website, see #22.)
  • Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan. Combinatorics: The Rota Way. Cambridge, 2009.

  • Graham Brightwell and Peter Winkler. Counting Linear Extensions. Order 8:225-242, 1991. doi

  • Thomas Browning, Max Hopkins, and Zander Kelley. Doppelgangers: the Ur-Operation and Posets of Bounded Height. arXiv:1710.140407

category: combinatorics

  1. Note that the definition we use for Z P(n)Z_P(n) has an index shift from the definition that seems to be more standard in combinatorics (see the footnote at zeta polynomial), so this equation is sometimes expressed as Ω P(n)=Z P (n)\Omega_P(n) = Z_{P^\downarrow}(n).

Last revised on August 26, 2018 at 12:21:18. See the history of this page for a list of all contributions to it.