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?

  • 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.

  • 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