Linear extension majority cycles in height-1 orders (Q920119)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4162944
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Linear extension majority cycles in height-1 orders |
scientific article; zbMATH DE number 4162944 |
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
0.8590452671051025
0 references
0.8109202980995178
0 references
0.8089579939842224
0 references
0.7746313214302063
0 references