✦ LIBER ✦

The number of linear extensions of subset ordering

✍ Scribed by Jichang Sha; D.J. Kleitman

Publisher: Elsevier Science
Year: 1987
Tongue: English
Weight: 520 KB
Volume: 63
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(87)90016-1

No coin nor oath required. For personal study only.

✦ Synopsis

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)).

📜 SIMILAR VOLUMES

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

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

On the family of linear extensions of a

On the family of linear extensions of a partial order

✍ Peter C Fishburn 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 170 KB

Exact order of subsets of asymptotic bas

Exact order of subsets of asymptotic bases in additive number theory

✍ Xing-De Jia 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 422 KB

On the Number of Precolouring Extensions

✍ Klaus Dohmen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 82 KB

We investigate the number of proper λ-colourings of a hypergraph extending a given proper precolouring. We prove that this number agrees with a polynomial in λ for any sufficiently large λ, and we establish a generalization of Whitney's broken circuit theorem by applying a recent improvement of the

On linear extension majority graphs of p

On linear extension majority graphs of partial orders

✍ Peter C Fishburn 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 279 KB