๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximating the number of linear extensions

โœ Scribed by Kevin Ewacha; Ivan Rival; Nejib Zaguia

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
737 KB
Volume
175
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

We approximate the number of linear extensions of an ordered set by counting "critical" suborders.

๐Ÿ“œ 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)).

The number of linear extensions of bipar
The number of linear extensions of bipartite graphs
โœ Grzegorz Stachowiak ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 124 KB

The number of linear extensions among the orientations of a bipartite graph is maximum just if the orientation itself is bipartite, the natural one.

Randomk-dimensional orders: Width and nu
Randomk-dimensional orders: Width and number of linear extensions
โœ Graham Brightwell ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 554 KB

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