Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3290301.pdf (2MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Some Extremal Problems on Graphs and Partial Orders
Author(s):Liu, Qi
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Mathematics
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.
Issue Date:2007
Type:Text
Language:English
Description:81 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007.
URI:http://hdl.handle.net/2142/86887
Other Identifier(s):(MiAaPQ)AAI3290301
Date Available in IDEALS:2015-09-28
Date Deposited:2007


This item appears in the following Collection(s)

Item Statistics