A note on merging (Q1068860)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A note on merging
scientific article

    Statements

    A note on merging (English)
    0 references
    0 references
    0 references
    1985
    0 references
    Let P be a finite poset and L the set of linear extensions of P. For x,y\(\in P\), let \(L(x>y)\subseteq L\) be the set of those linear extensions \(\sigma\) for which \(\sigma (x)>\sigma (y)\). Let \(\delta\) (P) be the maximum \(\delta\leq 1/2\) such that there exists a pair x,y\(\in P\) with \(\delta \leq | L(x>y)| /| L| \leq 1-\delta\). \textit{N. Linial} [SIAM J. Comp. 13, 795-801 (1981; Zbl 0548.68065)] has shown that any finite poset P of width 2 satisfies \(\delta\) (P)\(\geq 1/3\). The disjoint union \(C_ 1\cup C_ 2\) of a 1-element chain with a 2-element chain shows that the bound 1/3 cannot be further increased. In the paper under review, the extremal case is characterized. The author proves the following theorem: Let P be a poset of width 2. Then \(\delta (P)=1/3\) iff P is an ordinal sum of \(C_ 1\cup C_ 2's\) and \(C_ 1's\).
    0 references
    sorting, merging
    0 references
    finite poset
    0 references
    linear extensions
    0 references
    width
    0 references
    ordinal sum
    0 references

    Identifiers