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

2020/01/10 by Ivan Bochkov, Bochkov, I. A., Fedor Petrov +1
Mathematics · Medicine · #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Cholesterol and Lipid Metabolism #Combinatorics (math.CO) #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2001.03670

openalex publication_date 2020/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

Let (P,\leqslant) be a finite poset. Define the numbers a₁,a₂,… (respectively, c₁,c₂,…) so that a₁+…+a_k (respectively, c₁+…+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 ∏ a_i! and not more than n!/∏ c_i!. A corollary: if P is partitioned onto disjoint antichains of size b₁,b₂, …, then e(P)\geqslant ∏ b_i!.

Related

• Linear extensions of finite posets
• Poset probability in two-row partition posets
• Counting linear extensions of restricted posets
• Linear extension numbers of n-element posets
• Exponential functions of finite posets and the number of extensions with a fixed set of minimal points