𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Randomk-dimensional orders: Width and number of linear extensions

✍ Scribed by Graham Brightwell

Publisher
Springer Netherlands
Year
1992
Tongue
English
Weight
554 KB
Volume
9
Category
Article
ISSN
0167-8094

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the width Wk(n) and number Lk(n) of linear extensions of a random k-dimensional order P,Jn). We show that, for each fixed k, almost surely w&n) lies between (G/2 -C)n' -'lk and 4kn' Ilk, for some constant C, and Lk(n) lies between (e -%' -"")n and (2kn' -"k)n. The bounds given also apply to the expectations of the corresponding random variables.

We also show that Wk(n) and log Lk(n) are sharply concentrated about their means.

Mathematics

Subject Classificatioos (191). 06AO7, 6OCO5.

πŸ“œ SIMILAR VOLUMES

The number of linear extensions of subse
The number of linear extensions of subset ordering
✍ Jichang Sha; D.J. Kleitman πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 520 KB

We find asymptotic upper and lower bounds on the number of linear extensions of the containment ordering of subsets of a finite set. These agree in their most significant non-trivial terms. A related open question is described. L > 2"((n + 1)log 2 -4 log 2m -5 + o(1 ln)).