Weak-order extensions of an order

DOI10.1007/BFB0024488MaRDI QIDQ4373670zbMATH OpenFDO

Authors Karell Bertet, Jens Gustedt, M. Morvan

Publication date 16 February 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0024488

zbMATH Keywords

algorithmcomparability invariantgraph representationpartially ordered setweak-order extensions

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Review text

The authors are interested in an algorithmic and structural study of extensions of a partially ordered set. At first they describe a graph representing all the weak-order extensions of a partially ordered set and an algorithm generating them. Further they present a one-to-one correspondence between all the weak-order extensions of an order and all the paths from the unique source to the unique sink of a certain graph. This result is related to a similar characterization of linear and minimal interval extensions. Finally they prove that the number of weak-order extensions of a partially ordered set is a comparability invariant whereas the number of minimal weak-order extensions of a partially ordered set is not a comparability invariant. For the entire collection see [Zbl 0877.00011].

Recommendations

• Weak-order extensions of an order.
• On extensions, linear extensions, upsets and downsets of ordered sets
• On extensions, linear extensions, upsets and downsets of ordered sets (extended abstract)
• On the generation of extensions of a partially ordered set
• On the random generation and counting of weak order extensions of a poset with given class cardinalities

Cited in

(12)

• \(N\)-free orders and minimal interval extensions
• A theorem on order extensions: Embeddability of a system of weak orders to meet solvability constraints
• Weak-order extensions of an order.
• Weakly *-ordered *-fields
• Non-standard extensions of weak presentations
• scientific article; zbMATH DE number 4214076 (Why is no real title available?)
• scientific article; zbMATH DE number 4027523 (Why is no real title available?)
• On the generation of extensions of a partially ordered set
• WEAK EXTENDED ORDER ALGEBRAS HAVING ADJOINT TRIPLES
• On extensions, linear extensions, upsets and downsets of ordered sets
• Heigth preserving minimal interval extensions
• On the semilattice of weak orders of a set

This page was built for publication: Weak-order extensions of an order

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