2012 | OriginalPaper | Chapter
News about Semiantichains and Unichain Coverings
Authors : Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki
Published in: Computer Science – Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
P
×
Q
are equal. As a positive result we state conditions on
P
and
Q
that imply the min-max relation. However, we also have an example showing that in general the min-max relation is false. This disproves the Saks-West conjecture.