On linear extensions of ordered sets with a symmetry

DOI10.1016/0012-365X(87)90005-7MaRDI QIDQ1085187zbMATH OpenOpenAlexFDO

Authors Bernhard Ganter, Gerhart Häfner, Werner Poguntke

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(87)90005-7

zbMATH Keywords

automorphismcovering graphfinite ordered setlinear extensionssorting

Mathematics Subject Classification ID

Partial orders, general (06A06) Searching and sorting (68P10)

Review text

A linear extension of a finite ordered set \((P,<)\) is an order-preserving bijection \(\lambda\) : \(P\to \{1,2,...,| P| \}\). For any pair x, y of distinct elements in P, \(p(x<y)\) denotes the fraction of linear extensions such that \(\lambda (x)<\lambda (y)\). The authors prove the following theorem: Let \((P,<)\) be a finite cycle-free ordered set, and let \(\alpha\) be a non-trivial automorphism of \((P,<)\). Then \(p(x<\alpha (x))=1/2\) for any \(x\in P\) with \(\alpha\) (x)\(\neq x\). The motivation for this comes from sorting problems.

Recommendations

• scientific article; zbMATH DE number 924935
• scientific article; zbMATH DE number 3877241
• Linear extensions and order polynomials of finite partially ordered sets
• On a class of partially ordered sets and their linear invariants
• On extensions, linear extensions, upsets and downsets of ordered sets
• Linear extensions and comparable pairs in partial orders
• On extensions of constructive linear orders
• On the Linearity of Order-isomorphisms
• On linear extensions of finite posets
• Russian Text Ignored

Cites work

• A fixed point theorem for finite partially orderes sets
• Balancing poset extensions
• scientific article; zbMATH DE number 3909739 (Why is no real title available?)
• scientific article; zbMATH DE number 3771663 (Why is no real title available?)
• On linear extension majority graphs of partial orders
• On the family of linear extensions of a partial order
• The Information-Theoretic Bound is Good for Merging

Cited in

(11)

• A family of partially ordered sets with small balance constant
• On the \(1/3-2/3\) conjecture
• The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest
• On extensions, linear extensions, upsets and downsets of ordered sets (extended abstract)
• Sorting probability for large Young diagrams
• Cycle-free cuts of mutual rank probability relations.
• Every self-dual ordering has a self-dual linear extension
• Linear extension majority cycles on partial orders
• Linear extension majority cycles in height-1 orders
• Linear extension majority cycles for small (n\(\leq 9)\) partial orders
• Counting linear extension majority cycles in partially ordered sets on up to 13 elements

This page was built for publication: On linear extensions of ordered sets with a symmetry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085187)