Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Antichains and linear extensions - MaRDI portal

Antichains and linear extensions (Q1300333)

From MaRDI portal





scientific article; zbMATH DE number 1333344
Language Label Description Also known as
English
Antichains and linear extensions
scientific article; zbMATH DE number 1333344

    Statements

    Antichains and linear extensions (English)
    0 references
    0 references
    0 references
    7 September 1999
    0 references
    For any poset \(P\), let \(L(P)\) be the set of linear extensions of \(P\). Let \(m\geq 2\) be an integer and \(A\) be a finite set disjoint from \(\{1,2,\dots,m\}\). Denote by \(S(m,A)\) the family of posets \(P\) with the underlying set \(\{1,2,\dots,m\}\cup A\) in which \(\{1,2,\dots,m\}\) is an antichain. For \(P\in S(m,A)\) denote by \(L_m(P)\) the subset of \(L(P)\) whose linear extensions have \(1>2>\cdots>m\). The author deals with the problem of naximizing the number \(r(P)=|L_m(P)|/ |L(P)|\) over \(S(m,A)\) for fixed \(m\) and \(|A|\). He gives related results for \(|A|\in \{1,2\}\) and \(m\geq 2\).
    0 references
    linear extensions
    0 references
    posets
    0 references
    antichain
    0 references

    Identifiers