1
$\begingroup$

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain (containing $k$ points and with length $(k-1)$). I'm aware that various sources (e.g., Handbook of Enumerative Combinatorics by Bona, 2015) show that $$\Omega_P(k)=a_nk^n+a_{n-1}k^{n-1}+\ldots+a_1k+a_0,$$

where $n=|P|$ and $a_n=e(P)/|P|!$. Here, $e(P)$ denotes the number of linear extensions of $P$. My question is, what else is known about the remaining coefficients $a_{n-1},\ldots,a_1,a_0$? In particular, I am assuming that $n=k$ (thus thinking of both the poset and the chain length as functions of $n$), and am hoping to prove something of the form

$$\Omega_P(n)=\Theta(n^n),$$

which will be useful.

Besides the main problem, I am also interested in any known closed form expressions of order polynomials for special classes of posets. (E.g., if $P=P_{N,r}$, the graded disjoint union of $N$ chains having $r$ elements each, then $\Omega_P(k)={r+k-1\choose k-1}^N$; see Reiner, Stanton and Welker 2003)

(P.S. I posted this on StackExchange earlier, but realised that there weren't any specific tags that would facilitate the reach of the question to the hands of the appropriate audience.)

$\endgroup$
7
  • $\begingroup$ This fits into the larger setting of Ehrhart polynomials of lattice polytopes. The order polynomial is the Ehrhart polynomial of the order polytope. $\endgroup$
    – F. C.
    Commented Aug 27, 2015 at 20:00
  • $\begingroup$ I would say "various sources $\dots$ show $\dots$" rather than "suggest." I don't understand your question about $\Theta(a_nk^n)$. Are you fixing $P$ and letting $k\to\infty$? Every polynomial $f(k)$ of degree $n$ satisfies $f(k)=\Theta(k^n)$. $\endgroup$ Commented Aug 27, 2015 at 21:55
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because this already has an answer on MSE. $\endgroup$
    – Asaf Karagila
    Commented Aug 27, 2015 at 22:00
  • $\begingroup$ Thank you for the comments. In the actual problem, we are taking $k=n$ (the poset $P$ and the chain $\mathbf{k}$ are related). Thus, the answer I am looking for isn't quite the one given in MSE. $\endgroup$ Commented Aug 27, 2015 at 22:01
  • 3
    $\begingroup$ There are basic rules to follow when posting a question on several sites. The first one being: Don't order pizza from two places at once just because you're hungry. $\endgroup$
    – Asaf Karagila
    Commented Aug 27, 2015 at 22:03

0