One of the most celebrated results in algebraic combinatorics is the Hook Length Formula of Frame-Robinson-Thrall which counts the number of standard Young tableaux of given partition shape. Such SYTs can be viewed as linear extensions of a poset (namely, the poset of the shape). There are also product formulas enumerating SYTs of shifted shape, and linear extensions of tree posets. In fact, Proctor has defined a family of finite posets, called the "d-complete posets", which are defined axiomatically and which all enjoy a hook length-style product formula enumerating their linear extensions. See e.g. https://arxiv.org/abs/1704.05792. The d-complete posets include "all major examples" of posets with product formulas enumerating their linear extensions, as far as I am aware. (EDIT: This might be overselling the unifying power of the d-complete class; see the comments.)

If $P$ is a finite poset then its order polynomial $\Omega_P(m)$ is defined by $$\Omega_P(m) := \# \textrm{ weakly order preserving maps $P\to \{1,2,\ldots,m\}$}.$$ It is known that $\Omega_P(m)$ is a polynomial of degree $\#P$ and its leading coefficient is $1/\#P!$ times the number of linear extensions of $P$. ($\Omega_P(m)$ is basically the Ehrhart polynomial of the order polytope of $P$.) Certain posets have product formulas for their order polynomials. For instance, this is true of the rectangle poset $P = [a] \times [b]$ for which we have the celebrated formula of MacMahon: $$ \Omega_P(m) = \prod_{i=1}^{a} \prod_{j=1}^{b} \frac{i+j+m-2}{i+j-1}.$$ And there are similar product formulas for the order polynomials of all the minuscule posets (see https://www.sciencedirect.com/science/article/pii/S0195669884800372; in fact, the minuscule posets have a product formula for a $q$-analog of their order polynomials). But this is true also for instance of the root poset $P=\Phi^+(A_n)$ of the Type A root system which has $$\Omega_{P}(m) = \prod_{1\leq i \leq j \leq n} \frac{i+j+2m-2}{i+j}$$ (see https://www.sciencedirect.com/science/article/pii/S019566981380128X). More generally, the root posets of coincidental type have product formulas for their order polynomials (see S4.6.1 of https://conservancy.umn.edu/bitstream/handle/11299/159973/Williams_umn_0130E_14358.pdf).

Question: Is there a framework analogous to the framework of d-complete posets which explains when posets have product formulas for their order polynomials (at least for the "major examples" discussed above)?


I am adding a very closely related question which I am also quite interested in: how many posets have product formulas for their order polynomials, anyways?

Simpler Question: Are there any families of posets which have product formulas for their order polynomials, beyond the following?:

  • minuscule posets,
  • root posets of coincidental type ($\Phi^+(A_n)$, $\Phi^+(B_n)$, $\Phi^+(H_3)$, and $\Phi^+(I_2(\ell))$),
  • the ``trapezoid poset'', which has the same order polynomial as the rectangle.

For instance, tree/forest posets have a very simple structure and have a known hook-length style formula enumerating their linear extensions, but I wasn't able to figure out a product formula for their order polynomials.


I experimentally found a conjectural additional family of posets having order polynomial product formulas (the ``shifted double staircases'') and I asked for a proof in this follow-up question.

  • 2
    $\begingroup$ Some "minor" (i.e., nonmajor) examples of posets with product formulas for their number of linear extensions are at arxiv.org/pdf/1011.0795.pdf and arxiv.org/pdf/1409.1317.pdf. $\endgroup$ – Richard Stanley Jul 31 '19 at 23:57
  • $\begingroup$ @RichardStanley: good point about these exceptional skew shapes! So the theory for linear extension product formulas is less unified than I was implying. $\endgroup$ – Sam Hopkins Aug 1 '19 at 0:05
  • 1
    $\begingroup$ More generally, the Naruse hook-length formula for skew shapes, which is a sum of products, suggests to me that there could be other exceptional skew shapes where the Naruse formula "accidentally" simplifies to a single product. So for a really satisfying general framework, one might need to think in terms of Naruse-style formulas and not just product formulas. $\endgroup$ – Timothy Chow Aug 1 '19 at 14:21
  • 1
    $\begingroup$ You might want to look at example 8 and 9 here: arxiv.org/pdf/1609.00647.pdf This shows that the multiset of hook values are in general not enough to determine the order polynomial (this is true also for Young diagrams, where also the content plays a part). So, for trees, a type of content is needed... $\endgroup$ – Per Alexandersson Sep 28 '19 at 17:18
  • 3
    $\begingroup$ There is a product formula for the order polynomial of an unusual poset in "Solution of an Enumerative Problem Connected with Lattice Paths" by Kreweras and Niederhausen, sciencedirect.com/science/article/pii/S0195669881800200 though I don't know for sure that it's not included in those already mentioned. The poset is a product of a chain with a 3-element "V-shaped" poset. $\endgroup$ – Ira Gessel Oct 3 '19 at 3:10

There is a product formula for the order polynomial of an unusual poset in Solution of an Enumerative Problem Connected with Lattice Paths by Kreweras and Niederhausen, The poset is a product of a chain with a 3-element "V-shaped" poset.

  • 1
    $\begingroup$ Thanks so much for the reference! This "V cross chain" poset is really intriguing, and it seems to maybe have been overlooked in the years since this paper was published. It (experimentally) exhibits some remarkable integrability properties: e.g., 2*#P iterations of promotion of linear extensions is the identity (and #P iterations is the transposition symmetry of the poset); and it also seems to behave amazingly well with respect to "piecewise linear rowmotion" (arxiv.org/abs/1310.5294). $\endgroup$ – Sam Hopkins Oct 6 '19 at 17:10

Bob Proctor sent me an email explaining that the poset $P$ corresponding to the (unshifted, straight) shape $\lambda = (p+(r-1)b, p+(r-2)b, ..., p+b, p)$ has a product formula for its order polynomial, which can be seen via manipulations on the appropriate determinant. Note that this class includes both rectangles ($b=0$), as well as staircases ($p=1$, $b=1$). A reference for this result (with attribution to Proctor) is Stanley's EC2 Exercise 7.101. It is also mentioned in Proctor's paper "Odd symplectic groups."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.