News about semiantichains and unichain coverings.

DOI10.1007/978-3-642-30642-6_5zbMATH Open1344.06001arXiv1401.1225OpenAlexW150545534MaRDI QIDQ2907485FDOQ2907485

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)

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.

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

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

zbMATH Keywords

products of posetssemiantichainsunichain coveringsposet dualitySaks-West conjecture

Mathematics Subject Classification ID

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

Cites Work

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

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)