Penman, DB and McDiarmid, CJH and Iliopoulos, V (2018) Linear Extensions and Comparable Pairs in Partial Orders. Order, 35 (3). pp. 403-420. DOI https://doi.org/10.1007/s11083-017-9439-y
Penman, DB and McDiarmid, CJH and Iliopoulos, V (2018) Linear Extensions and Comparable Pairs in Partial Orders. Order, 35 (3). pp. 403-420. DOI https://doi.org/10.1007/s11083-017-9439-y
Penman, DB and McDiarmid, CJH and Iliopoulos, V (2018) Linear Extensions and Comparable Pairs in Partial Orders. Order, 35 (3). pp. 403-420. DOI https://doi.org/10.1007/s11083-017-9439-y
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 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 Faculty of Science and Health > Mathematical Sciences, Department of |
| SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 09 Oct 2017 13:47 |
| Last Modified: | 06 Jan 2022 13:42 |
| URI: | http://repository.essex.ac.uk/id/eprint/20456 |
Available files
Filename: M:\ORDE-D-16-00030_R3.pdf