15
$\begingroup$

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)?

EDIT:

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.

EDIT 2:

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.

Improve this question
$\endgroup$
10
  • 3
    $\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
    Commented Jul 31, 2019 at 23:57
  • 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
    Commented Aug 1, 2019 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
    Commented Sep 28, 2019 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
    Commented Oct 3, 2019 at 3:10
  • 1
    $\begingroup$ In case you're curious, the number of nonisomorphic $n$-element posets whose order polynomial factors into linear factors over $\mathbb{Q}$, for $1\leq n\leq 8$, is given by 1, 2, 5, 14, 31, 111, 257, 624. $\endgroup$
    – Richard Stanley
    Commented Jul 13, 2020 at 2:35

4 Answers 4

Reset to default
4
$\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. The poset is a product of a chain with a 3-element "V-shaped" poset.

Improve this answer
$\endgroup$
1
  • 2
    $\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
    Commented Oct 6, 2019 at 17:10
2
$\begingroup$

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."

Improve this answer
$\endgroup$
2
$\begingroup$

I wrote a survey of posets with order polynomial product formulas. It does not provide a "unified framework" for these posets, but does put forward a heuristic that they are the posets with good dynamical behavior.

Improve this answer
$\endgroup$
0
$\begingroup$

There are product formulas for the linear extensions of forests also, and some q-analogs of these. Perhaps the order-polynomials are nice as well.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In the original question I mentioned forests and that I tried to look at them a little bit but could not see anything nice. $\endgroup$
    – Sam Hopkins
    Commented Jun 15, 2020 at 19:58
  • 2
    $\begingroup$ In particular, it seems from the examples that having an order polynomial product formula is much, much rarer than having a linear extensions product formula. Compare: many interesting lattice polytopes (Chan-Robbins-Yuen polytope, flow polytopes of certain graphs, etc.) have product formulas for their volumes, but almost none have product formulas for their entire Ehrhart polynomials. $\endgroup$
    – Sam Hopkins
    Commented Jun 15, 2020 at 20:00
  • $\begingroup$ @SamHopkins Ah, you are right - I recall I have an example where the hook-lengths do not uniquely determine the Ehrhart-polynomial for trees, so indeed, this rules out some nice properties. $\endgroup$
    – Per Alexandersson
    Commented Jun 15, 2020 at 20:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .