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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    preorder
    0 references
    linear extensions
    0 references
    cycle
    0 references
    posets of height 1
    0 references