𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Inequalities for the number of linear extensions

✍ Scribed by A. Sidorenko

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

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximating the number of linear exten
Approximating the number of linear extensions
✍ Kevin Ewacha; Ivan Rival; Nejib Zaguia πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 737 KB

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

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.

Geometrical Techniques for Estimating Nu
Geometrical Techniques for Estimating Numbers of Linear Extensions
✍ BΓ©la BollobΓ‘s; Graham Brightwell; Alexander Sidorenko πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 126 KB

Let P be a two-dimensional order, and P any complement of P, i.e., any partial order whose comparability graph is the complement of the comparability graph of P. Let e(Q) denote the number of linear extensions of the partial order Q. Sidorenko [13] showed that e(P)e(P) β‰₯ n!, for any two-dimensional