Let $P$ be a graded poset with rank function $r$. We may then define its rank-polynomial as:

$R_P(q) = \sum_{x \in P} q^{r(x)}$.

This definition can be applied to several interesting posets, for instance:

  • when $P$ is the Boolean lattice over $n$ elements, we have $R_P(q) = \sum_{i = 0}^{n} \binom{n}{i} q^i = (1+q)^n$,

  • when $P$ is the $n$-permutohedron, we have $R_P(q) = \prod_{i = 1}^{n} [i]_q$, where by convention $[n]_q = \sum_{i = 0}^{n-1} q^i$.

  • more generally, when $G \subseteq S_n$ is a permutation group with basis $B$, we may define the rank of an element $x \in G$ as the length of a minimum decomposition of $x$ over $B$.

The last case seems the most interesting: is it then possible to compute $R_P(q)$ in polynomial time given a presentation of $G$?

Also, are there other examples of graded posets for which a closed formula is known?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.