Research Repository

Linear Extensions and Comparable Pairs in Partial Orders

Penman, DB and McDiarmid, CJH and Iliopoulos, V (2017) 'Linear Extensions and Comparable Pairs in Partial Orders.' Order. ISSN 0167-8094

M:\ORDE-D-16-00030_R3.pdf - Accepted Version

Download (769kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: Partial orders, Linear extensions, Comparable pairs, Concentration inequalities
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 09 Oct 2017 13:47
Last Modified: 14 Oct 2018 01:00

Actions (login required)

View Item View Item