Some Extremal Problems on Graphs and Partial Orders
type: CreativeWork
description: A unichain in a product poset P x Q is a chain in which the value of one coordinate is fixed. A semiantichain in P x Q is a family S such that (u, v) < ( u', v') for two elements of S only if u < u' and v < v' . Saks and West conjectured that for every product of partial orders, the maximum size of a semiantichain equals the minimum number of unichains needed to cover the product. We prove the case where both factors have width 2. We also use the characterization of product graphs that are perfect to prove other special cases, including the case where both factors have height 2. Finally, we make an observation about the case where both factors have dimension 2.
abstract: A unichain in a product poset P x Q is a chain in which the value of one coordinate is fixed. A semiantichain in P x Q is a family S such that (u, v) < ( u', v') for two elements of S only if u < u' and v < v' . Saks and West conjectured that for every product of partial orders, the maximum size of a semiantichain equals the minimum number of unichains needed to cover the product. We prove the case where both factors have width 2. We also use the characterization of product graphs that are perfect to prove other special cases, including the case where both factors have height 2. Finally, we make an observation about the case where both factors have dimension 2.
author: Liu, Qi
language: eng
keywords: Mathematics
date published: 2015-09-28T15:20:00Z
date modified: 2026-07-22T22:26:28Z
provider: University of Illinois - Urbana-Champaign
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Illinois at Urbana-Champaign

PropertyValue
property ID: Handle
value: http://hdl.handle.net/2142/86887