Linear extension majority cycles in height-1 orders (Q920119)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear extension majority cycles in height-1 orders |
scientific article |
Statements
Linear extension majority cycles in height-1 orders (English)
0 references
1990
0 references
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.
0 references
preorder
0 references
linear extensions
0 references
cycle
0 references
posets of height 1
0 references