News about semiantichains and unichain coverings.

DOI10.1007/978-3-642-30642-6_5MaRDI QIDQ2907485zbMATH OpenOpenAlexFDO

Authors Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki

Publication date 10 September 2012

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.1225

zbMATH Keywords

products of posetssemiantichainsunichain coveringsposet dualitySaks-West conjecture

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: We study a min-max relation conjectured by Saks and West: For any two posets $P$ and $Q$ the size of a maximum semiantichain and the size of a minimum unichain covering in the product $PimesQ$ are equal. For positive we state conditions on $P$ and $Q$ that imply the min-max relation. Based on these conditions we identify some new families of posets where the conjecture holds and get easy proofs for several instances where the conjecture had been verified before. However, we also have examples showing that in general the min-max relation is false, i.e., we disprove the Saks-West conjecture.

Recommendations

• On the duality of semiantichains and unichain coverings.
• Two properties of maximal antichains in strict chain product posets
• Duality for semiantichains and unichain coverings in products of special posets
• Maximum antichains in the product of chains
• Networks and chain coverings in partial orders and their products

Cites work

• scientific article; zbMATH DE number 3884163 (Why is no real title available?)
• scientific article; zbMATH DE number 1296818 (Why is no real title available?)
• scientific article; zbMATH DE number 863477 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A short proof of the existence of k-saturated partitions of partially ordered sets
• Duality for semiantichains and unichain coverings in products of special posets
• Matchings, cutsets, and chain partitions in graded posets
• Nested chain partitions of LYM posets
• Networks and chain coverings in partial orders and their products
• On chains and Sperner k-families in ranked posets
• On nested chain decompositions of normalized matching posets of rank 3
• Semiantichains and Unichain Coverings in Direct Products of Partial Orders
• Some partitions associated with a partially ordered set
• Sufficient Conditions for a Symmetric Chain Order
• The structure of Sperner k-families
• Two easy duality theorems for product partial orders
• Unichain coverings in partial orders with the nested saturation property

Cited in

(3)

• On the duality of semiantichains and unichain coverings.
• Networks and chain coverings in partial orders and their products
• Unichain coverings in partial orders with the nested saturation property

This page was built for publication: News about semiantichains and unichain coverings.

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