Linear extensions of random orders
✍
Graham Brightwell
📂
Article
📅
1994
🏛
Elsevier Science
🌐
English
⚖ 621 KB
A popular model of random orders is obtained by taking two disjoint n-element antichains A, and Al, and putting in each relation in A, x A, with probability l/2, all the choices being made independently. We estimate the number of linear extensions of such an ordered set, showing that this number is