The Bounds for the Number of Linear Extensions Via Chain and Antichain Coverings
- PDF / 231,355 Bytes
- 6 Pages / 439.642 x 666.49 pts Page_size
- 4 Downloads / 138 Views
The Bounds for the Number of Linear Extensions Via Chain and Antichain Coverings I. A. Bochkov1 · F. V. Petrov1,2 Received: 7 March 2020 / Accepted: 5 October 2020 / © Springer Nature B.V. 2020
Abstract Let (P , ) be a finite poset. Define the numbers a1 , a2 , . . . (respectively, c1 , c2 , . . .) so that a1 + . . . + ak (respectively, c1 + . . . + ck ) 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 ai ! and not more than n!/ c i !. A corollary: if P is partitioned onto disjoint antichains of sizes b1 , b2 , . . ., then e(P ) bi !. Keywords Chains covering · Antichains covering · Linear extension
1 Introduction Let (P , ) be a finite poset. In a recent paper [9] the following double inequality for the number e(P ) of linear extensions of P is applied. Partition P onto disjoint antichains P = A1 A2 A3 . . . , where Ai is the antichain of elements x such the max(|C| : C is a chain, max(C) = x) = i. Also partition P in arbitrary way onto disjoint chains P = C1 C2 C3 . . .. Then n! e(P ) |Ai |! (1) |Ci |! To quote [9]: “These bounds are probably folklore; for the lower bound see e.g [7].” We prove that the right inequality in Eq. 1 holds for arbitrary antichain partition. We also improve both inequalities in terms of Greene–Kleitman–Fomin parameters, which we define now. The GKF antichain parameters a1 a2 . . . of a finite poset P are defined as follows: a1 +. . .+ak is the maximal number of elements of P which may be covered by k antichains F. V. Petrov
[email protected] I. A. Bochkov [email protected] 1
St. Petersburg State University, Saint Petersburg, Russia
2
St. Petersburg Department of V. A. Steklov Mathematical Institute RAS, St. Petersburg State University, Saint Petersburg, Russia
Order
(k = 1, 2, . . .). The fact that the sequence (ai ) is weakly decreasing is a part of Greene– Kleitman–Fomin theorem [2, 3]. Another claim of this theorem is the chains-antichains duality: for the partition n = c1 + c2 + . . ., conjugate to the partition n = a1 + a2 + . . ., the sum c1 +. . .+ck is the maximal number of elements of P which may be covered by k chains. The numbers c1 , c2 , . . . are called GKF chain parameters of poset P . The computation of GKF parameters is in P, since it reduces to the minimum-cost flow problem [4]. The main result of this paper is Theorem 1
n! e(P ) ai ! ci !
(2)
i
Note that Eq. 2 implies Eq. 1, see Corollary 6 and Remark 8.
2 Majorization lemmata Let X be a finite multiset consisting of non-negative numbers. For non-negative integer k define sk (X) as the sum of min(k, |X|) maximal elements of multiset X; also denote s(X) = s|X| (X) the sum of all elements of X. We say that multiset X majorizes another multiset Y of non-negative numbers and write X Y if s(X) = s(Y ) and sk (X) sk (Y ) for all k. Note that the usual definition of majoriazation includes the requirement of |X| = |Y |. For our goals this is not con
Data Loading...
