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

Standard

The Bounds for the Number of Linear Extensions Via Chain and Antichain Coverings. / Bochkov, I. A.; Petrov, F. V.

In: Order, 22.10.2020.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{eba16eded65047b5b8a6f264dc9d22e0,

title = "The Bounds for the Number of Linear Extensions Via Chain and Antichain Coverings",

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! / ∏ ci!. A corollary: if P is partitioned onto disjoint antichains of sizes b1,b2,…, then e(P) ≥ ∏ bi!.",

keywords = "Antichains covering, Chains covering, Linear extension",

author = "Bochkov, {I. A.} and Petrov, {F. V.}",

note = "Funding Information: The work was supported by the Foundation for the Advancement of Theoretical Physics and Mathematics “BASIS”. Publisher Copyright: {\textcopyright} 2020, Springer Nature B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2020",

month = oct,

day = "22",

doi = "10.1007/s11083-020-09542-3",

language = "English",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Nature",

}

RIS

TY - JOUR

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

AU - Bochkov, I. A.

AU - Petrov, F. V.

N1 - Funding Information: The work was supported by the Foundation for the Advancement of Theoretical Physics and Mathematics “BASIS”. Publisher Copyright: © 2020, Springer Nature B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/10/22

Y1 - 2020/10/22

N2 - 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! / ∏ ci!. A corollary: if P is partitioned onto disjoint antichains of sizes b1,b2,…, then e(P) ≥ ∏ bi!.

AB - 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! / ∏ ci!. A corollary: if P is partitioned onto disjoint antichains of sizes b1,b2,…, then e(P) ≥ ∏ bi!.

KW - Antichains covering

KW - Chains covering

KW - Linear extension

UR - http://www.scopus.com/inward/record.url?scp=85092900227&partnerID=8YFLogxK

U2 - 10.1007/s11083-020-09542-3

DO - 10.1007/s11083-020-09542-3

M3 - Article

AN - SCOPUS:85092900227

JO - Order

JF - Order

SN - 0167-8094

ER -

ID: 75247476