Linear extensions and comparable pairs in partial orders
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 pro...
| Главные авторы: | , , |
|---|---|
| Формат: | Journal article |
| Опубликовано: |
Springer
2017
|
| _version_ | 1826257075819249664 |
|---|---|
| author | McDiarmid, C Penman, D Iliopoulos, V |
| author_facet | McDiarmid, C Penman, D Iliopoulos, V |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T18:12:22Z |
| format | Journal article |
| id | oxford-uuid:037850c6-466b-41c8-8a14-6e1cfc69ac52 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:12:22Z |
| publishDate | 2017 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:037850c6-466b-41c8-8a14-6e1cfc69ac522022-03-26T08:46:20ZLinear extensions and comparable pairs in partial ordersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:037850c6-466b-41c8-8a14-6e1cfc69ac52Symplectic Elements at OxfordSpringer2017McDiarmid, CPenman, DIliopoulos, VWe 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. |
| spellingShingle | McDiarmid, C Penman, D Iliopoulos, V Linear extensions and comparable pairs in partial orders |
| title | Linear extensions and comparable pairs in partial orders |
| title_full | Linear extensions and comparable pairs in partial orders |
| title_fullStr | Linear extensions and comparable pairs in partial orders |
| title_full_unstemmed | Linear extensions and comparable pairs in partial orders |
| title_short | Linear extensions and comparable pairs in partial orders |
| title_sort | linear extensions and comparable pairs in partial orders |
| work_keys_str_mv | AT mcdiarmidc linearextensionsandcomparablepairsinpartialorders AT penmand linearextensionsandcomparablepairsinpartialorders AT iliopoulosv linearextensionsandcomparablepairsinpartialorders |