Journal title
Order
DOI
10.1007/s11083-017-9439-y
Last updated
2022-03-05T06:58:17.217+00:00
Page
1-18
Abstract
© 2017 Springer Science+Business Media B.V. We study the number of linear extensions of a partial order with a given proportion of comparable pairs of elements, and estimate the maximum and minimum possible numbers. We also consider a random interval partial order on n elements, which has close to a third of the pairs comparable with high probability: we show that the number of linear extensions is n! 2−Θ(n) with high probability.
Symplectic ID
609722
Submitted to ORA
On
Publication type
Journal Article
Publication date
14 October 2017