{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/86887"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/86887","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Some Extremal Problems on Graphs and Partial Orders","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.","abstract_html":"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) &lt; ( u&#x27;, v&#x27;) for two elements of S only if u &lt; u&#x27; and v &lt; v&#x27; . 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_has_math":false,"creators":["Liu, Qi"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-28T15:20:00Z","date_published":"2015-09-28T15:20:00Z","updated_at":"2026-07-22T22:26:28Z","subjects":["Mathematics"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3290301"],"render_values":[{"text":"(MiAaPQ)AAI3290301","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/86887","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B."]},{"key":"dc:creator","label":"Author","values":["Liu, Qi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-28T15:20:00Z","10000-01-01","2007"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/86887","(MiAaPQ)AAI3290301"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2015-09-28T15:20:00Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3290301.pdf: 2487832 bytes, checksum: 53d6aca1638323998709dab480a3f627 (MD5) Previous issue date: 2007","Embargo set by: Seth Robbins for item 88168 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","81 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007."]},{"key":"dc:title","label":"Title","values":["Some Extremal Problems on Graphs and Partial Orders"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B."],"dc:creator":["Liu, Qi"],"dc:date":["2015-09-28T15:20:00Z","10000-01-01","2007"],"dc: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.","Made available in DSpace on 2015-09-28T15:20:00Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3290301.pdf: 2487832 bytes, checksum: 53d6aca1638323998709dab480a3f627 (MD5) Previous issue date: 2007","Embargo set by: Seth Robbins for item 88168 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","81 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007."],"dc:identifier":["http://hdl.handle.net/2142/86887","(MiAaPQ)AAI3290301"],"dc:language":["eng"],"dc:subject":["Mathematics"],"dc:title":["Some Extremal Problems on Graphs and Partial Orders"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:28Z"}