Standard

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

в: Order, 22.10.2020.

Результаты исследований: Научные публикации в периодических изданияхстатьяРецензирование

Harvard

APA

Vancouver

Author

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