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

      Identifiers