×

zbMATH — the first resource for mathematics

Linear extension majority cycles in height-1 orders. (English) Zbl 0708.06002
Let x, y be elements of the finite poset X, and write \(x>_ py\) to indicate that more linear extensions of the poset have x above y than y above x. Earlier work by Fishburn showed that when the height of X is \(\geq 2\) then \(>_ p\) can have a cycle. It has recently been shown by Gehrlein and Fishburn that the smallest poset having a \(>_ p\)-cycle has 9 elements, and that there are exactly 5 nonisomorphic 9-element posets having \(>_ p\)-cycles. The current work addresses the case of posets of height 1. If A denotes the set of maximal non-isolated elements, and B the set of minimal non-isolated elements, it is shown that any such cycle must lie entirely within A or entirely within B. If #A\(=3\), then there is no cycle within A. If #A\(=4\) the smallest poset of height 1 admitting a \(>_ p\)-cycle has 15 members. If #A\(=3\), the question is left open as to whether B can contain a cycle.
Reviewer: M.F.Janowitz

MSC:
06A06 Partial orders, general
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. C.Fishburn (1974) On the family of linear extensions of a partial order, J. Combin. Theory 17, 240-243. · Zbl 0288.06001 · doi:10.1016/0095-8956(74)90030-6
[2] P. C.Fishburn (1976) On linear extension majority graphs of partial orders, J. Combin. Theory 21, 65-70. · Zbl 0324.06002 · doi:10.1016/0095-8956(76)90028-9
[3] P. C.Fishburn (1986) Proportional transitivity in linear extensions of ordered sets, J. Combin. Theory Ser. B 41, 48-60. · Zbl 0566.06002 · doi:10.1016/0095-8956(86)90027-4
[4] B.Ganter, G.H?fner, and W.Poguntke (1987) On linear extensions of ordered sets with a symmetry, Discrete Math. 63, 153-156. · Zbl 0607.06001 · doi:10.1016/0012-365X(87)90005-7
[5] W. V. Gehrlein and P. C. Fishburn (1989) Linear extension majority cycles for small (n?9) partial orders, Comput. Math. Appl. (in press). · Zbl 0708.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.