The Bounds for the Number of Linear Extensions Via Chain and Antichain Coverings

摘要

Let (P, =) be a finite poset. Define the numbers a(1), a(2), ... (respectively, c(1), c(2), ... ) so that a(1) + ... + a(k) (respectively, c(1) + ... + c(k)) is the maximal number of elements of P which may be covered by k antichains (respectively, k chains.) Then the number e(P) of linear extensions of poset P is not less than Pi a(i) ! and not more than n!/ Pi c(i) !. A corollary: if P is partitioned onto disjoint antichains of sizes b(1), b(2), ... , then e(P) = Pi b(i) !.