5
$\begingroup$

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?

  • 0
    I take it you've looked at the paper I mentioned several days ago, and you have found it isn't useful?2011-08-14
  • 1
    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 :)2011-08-14
  • 0
    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.2011-08-15
  • 1
    I emailed professor Kahn about this. He said that he thinks http://arxiv.org/PS_cache/arxiv/pdf/0911/0911.0086v2.pdf is the state of the art right now.2011-08-25

1 Answers 1

2

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.

  • 1
    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.2011-08-14
  • 0
    It looks like some overlines where not rendered correctly. This makes my comment hard to understand, but I can't edit it anymore...2011-08-14