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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.