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
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