1
$\begingroup$

Using the hook formula, it is easy to compute the volume of order polytopes obtained from posets with partition shape, since this is the same as the number of linear extensions.

To my knowledge, computing the number of linear extensions of an arbitrary order polytope is #P-hard.

There is also the family of series-parallel posets, where computing the Ehrhart polynomial (and hence the volume) can be done in polynomial time, so there are natural families where computing the Ehrhart polynomial is easy.

My question is then: can one compute the Ehrhart polynomial of partition-shaped order polytopes quickly (and not just the volume)?

Poset

$\endgroup$
4
  • 2
    $\begingroup$ Isn't this equivalent to counting $P$-partitions of bounded maximal size? For this there is a determinantal formula known to MacMahon later generalized to skew shapes by Kreweras. $\endgroup$ Feb 25, 2016 at 16:58
  • 1
    $\begingroup$ See the note on pg 23 of: arxiv.org/abs/math/9908029v1. $\endgroup$ Feb 25, 2016 at 17:03
  • $\begingroup$ @SamHopkins: Ah, right, that makes sense! $\endgroup$ Feb 25, 2016 at 19:39
  • 2
    $\begingroup$ Of course, I should've just said "plane partitions" above, which is what $P$-partitions are in this case of $P$ :) $\endgroup$ Feb 25, 2016 at 19:53

1 Answer 1

1
$\begingroup$

The number of plane partitions of shape $\lambda/\mu$ with maximal entry at most $m$, is given by $$ \det\left( \binom{\lambda_i-\mu_j + m}{i-j+m} \right)_{i,j=1,\dotsc,\ell} $$ where $\ell = \ell(\lambda)$.

See Kreweras, Germain. Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers.

$\endgroup$
2
  • 1
    $\begingroup$ I saw this pop up and was about to point out that the case of straight shapes actually goes back to MacMahon, and then I saw my own comments from 4 years ago. :) $\endgroup$ May 28, 2020 at 13:05
  • 1
    $\begingroup$ By the way, a nice proof of this is via the Lindstrom-Gessel-Viennot lemma. $\endgroup$ May 28, 2020 at 14:25

Your Answer

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

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