nLab
zeta polynomial

Contents

Idea

The zeta polynomial Z P(n)Z_P(n) of a finite partially ordered set PP counts the number of multichains (also known as “weakly increasing sequences”) of length nn in PP.

Definition

By a multichain of length nn in PP, we mean a sequence of elements x 0x 1x nx_0 \le x_1 \le \cdots \le x_n, which can be identified with an order-preserving function from the linear order [n]={0<1<<n}[n] = \{ 0 \lt 1 \lt \cdots \lt n \} into PP. To see that

Z P(n)=|Hom([n],P)|Z_P(n) = |Hom([n],P)|

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

Z P(n)= k=0 db k(nk)Z_P(n) = \sum_{k=0}^{d} b_k \binom{n}{k}

where b kb_k is the number of chains x 0<x 1<<x kx_0 \lt x_1 \lt \cdots \lt x_k in PP (i.e., injective order-preserving functions from [k][k] to PP), and where dd is the length of the longest chain. Hence Z P(n)Z_P(n) is a polynomial of degree equal to the length of the longest chain in PP.

Examples

The zeta polynomial of [2]={0<1<2}[2] = \{ 0 \lt 1 \lt 2 \} is

3+3n+(n2)=n 2+5n+623 + 3n + \binom{n}{2} = \frac{n^2 + 5n + 6}{2}

For example, evaluating the polynomial at n=0n=0 and n=1n=1 confirms that [2][2] contains 3 points and 6 intervals, while evaluating it at n=2n=2 confirms that there are 10 order-preserving functions from [2][2] to itself.

The zeta polynomial of the 5-element poset

P= v u y z x P = \array{&&v&& \\ &&\uparrow&& \\ &&u&& \\ &\nearrow& &\nwarrow& \\ y &&&& z \\ &\nwarrow& &\nearrow& \\ &&x&&}

is 5+9n+7(n2)+2(n3)=2n 3+15n 2+37n+3065 + 9n + 7\binom{n}{2} + 2\binom{n}{3} = \frac{2n^3 + 15n^2 + 37n + 30}{6}. Evaluating at n=1n=1, we compute that PP contains 14 distinct intervals.

Properties

Relation to order polynomial

The order polynomial is related to the zeta polynomial by the equation

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

where P (2) PP^\downarrow \cong (2)^P is the lattice of lower sets in PP. 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 zeta function

Using the formalism of incidence algebras, the zeta polynomial has a simple expression in terms of the zeta function of PP (defined by ζ P(x,y)=1\zeta_P(x,y) = 1 if xyx\le y and ζ P(x,y)=0\zeta_P(x,y) = 0 otherwise):

Z P(n)= x,yPζ P n(x,y)Z_P(n) = \sum_{x,y\in P} \zeta_P^n(x,y)

where ζ P n\zeta_P^n is the nn-fold convolution product of ζ P\zeta_P. (In other words, if we view the zeta function as a square matrix, then the zeta polynomial is the sum of the entries in its nn-fold matrix product.) This follows immediately from the definition of the convolution product,

(fg)(x,y)= xzyf(x,z)g(z,y)(f\cdot g)(x,y) = \sum_{x \le z \le y} f(x,z) \cdot g(z,y)

since ζ P n(x,y)\zeta_P^n(x,y) computes the number of multichains of length nn in PP from xx to yy.

As a special case, if PP has both a bottom element 0 and a top element 1, then

Z P(n)=ζ P n+2(0,1)Z_P(n) = \zeta_P^{n+2}(0,1)

since an arbitrary multichain x 0x 1x nx_0 \le x_1 \le \cdots \le x_n of length nn can be extended to a multichain 0x 0x 1x n10 \le x_0 \le x_1 \le \cdots \le x_n \le 1 of length n+2n+2 between 0 and 1.

References

  • Paul H. Edeleman. Zeta Polynomials and the Möbius Function. European Journal of Combinatorics 1(4), 1980.
  • Richard P. Stanley, Enumerative combinatorics, vol.1 (pdf)
  • Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan. Combinatorics: The Rota Way. Cambridge, 2009.
category: combinatorics

  1. Note that the definition we use here for Z P(n)Z_P(n) has an index shift from the definition that seems to be more standard in combinatorics. For example, the definition in (Stanley, 3.12) counts multichains of length n2n-2 rather than of length nn. Accordingly, one should apply a substitution to get some of the properties stated here to match equivalent results in the literature.

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