The bounds for the number of linear extensions via chain and antichain coverings

preprint2020arXivOpen access

Abstract

Let (P,⩽)(\mathcal{P},\leqslant) be a finite poset. Define the numbers a1,a2,…a_1,a_2,\ldots (respectively, c1,c2,…c_1,c_2,\ldots) so that a1+…+aka_1+\ldots+a_k (respectively, c1+…+ckc_1+\ldots+c_k) is the maximal number of elements of P\mathcal{P} which may be covered by kk antichains (respectively, kk chains.) Then the number e(P)e(\mathcal{P}) of linear extensions of poset P\mathcal{P} is not less than ∏ai!\prod a_i! and not more than n!/∏ci!n!/\prod c_i!. A corollary: if P\mathcal{P} is partitioned onto disjoint antichains of size b1,b2,…b_1,b_2, \ldots, then e(P)⩾∏bi!e(\mathcal{P})\geqslant \prod b_i!.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.