Linear Extensions and Comparable pairs in Partial Orders

Colin McDiarmid, David Penman, Vasileios Iliopoulos

Published 2016-03-09Version 1

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 show that a random interval partial order on $n$ elements has close to a third of the pairs comparable with high probability, and the number of linear extensions is $n! \, 2^{-\Theta(n)}$ with high probability.