Name
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−Θ(n) with high probability. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/S11083-017-9439-Y | Order |
Keywords | Field | DocType |
Partial orders, Linear extensions, Comparable pairs, Concentration inequalities | Discrete mathematics,Combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 3 | 0167-8094 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| David B. Penman | 2 | 0 | 0.34 |
| Vasileios Iliopoulos | 3 | 2 | 1.05 |