Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 is the state of the art right now. – Jacopo Notarstefano Aug 25 '11 at 21:21
up vote 2 down vote accepted

Béla Bollobás, Graham Brightwell, and Alexander Sidorenko, Geometrical techniques for estimating numbers of linear extensions, European J. Combin. 20 (1999), no. 5, 329–335, MR1702372 (2000j:05007) improves on one of the results in the Kahn and Kim paper, though I'm not sure it improves on that particular bound.

share|cite|improve this answer
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
It looks like some overlines where not rendered correctly. This makes my comment hard to understand, but I can't edit it anymore... – Jacopo Notarstefano Aug 14 '11 at 21:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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