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

Improve this question
$\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$
    – Sam Hopkins
    Commented Feb 25, 2016 at 16:58
  • 1
    $\begingroup$ See the note on pg 23 of: arxiv.org/abs/math/9908029v1. $\endgroup$
    – Sam Hopkins
    Commented Feb 25, 2016 at 17:03
  • $\begingroup$ @SamHopkins: Ah, right, that makes sense! $\endgroup$
    – Per Alexandersson
    Commented 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$
    – Sam Hopkins
    Commented Feb 25, 2016 at 19:53

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Sam Hopkins
    Commented May 28, 2020 at 13:05
  • 1
    $\begingroup$ By the way, a nice proof of this is via the Lindstrom-Gessel-Viennot lemma. $\endgroup$
    – Sam Hopkins
    Commented May 28, 2020 at 14:25

You must log in to answer this question.

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