# Best known bounds for the number of linear extensions of a poset

Let $(P, \le)$ be a poset on $n$ elements $x_1\dots x_n$. A total order $<$ on the same set is said to be a linear extension of $\le$ if $(\forall i,j)\quad x_i \le x_j \rightarrow x_i < x_j$.

The problem of counting the number of linear extensions of a given poset is known to be $#P-complete$: this is proved in Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242.

In the same paper some bounds are given to estimate this number. These bounds are improved in Kahn, J.; Kim, J. H. (1992), "Entropy and sorting", Proocedings of the 24th Annual ACM Symposium on Theory of Computing: 178-187

Were these bounds improved again? What are the best known bounds for this problem?

-
I take it you've looked at the paper I mentioned several days ago, and you have found it isn't useful? – Gerry Myerson Aug 14 '11 at 9:18
No professor Myerson! I found it very useful. I put a bounty mostly because of the unusually low number of views. And because I wanted to try this feature :) – Jacopo Notarstefano Aug 14 '11 at 11:22
OK. If you don't get an answer here, maybe you should write to one of the authors of one of the papers to ask the question. – Gerry Myerson Aug 15 '11 at 1:19
I emailed professor Kahn about this. He said that he thinks arxiv.org/PS_cache/arxiv/pdf/0911/0911.0086v2.pdf is the state of the art right now. – Jacopo Notarstefano Aug 25 '11 at 21:21

Let $e(P)$ be the number of linear extensions of $P$. This paper gives bounds for the quantity $e(P)e(\overline P)$, where $P$ is a poset of dimension 2 and $\overline P$ is any poset whose comparability graph is the complement of the comparability graph of P. These bounds improve those that would be given from Kahn and Kim's theorems. On the other hand it's remarked that this does not give new bounds on the quantity $e(P)$. This paper is still useful, since in 1999 it remarks that Kahn and Kim's are the best known bounds for that quantity. Not exactly an answer to my question, but very close. – Jacopo Notarstefano Aug 14 '11 at 21:45