pith. sign in

arxiv: 1603.02901 · v3 · pith:UPISMCCAnew · submitted 2016-03-09 · 🧮 math.CO

Linear Extensions and Comparable Pairs in Partial Orders

classification 🧮 math.CO
keywords comparableextensionslinearpairspartialelementshighnumber
0
0 comments X
read the original abstract

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^{-\Theta(n)}$ with high probability.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.