{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22881"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22881","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimization on products of combinatorial structures","abstract":"We consider optimization problems on combinatorial structures with a product form. The independence number of a graph G, denoted $\\alpha (G)$, is the size of the largest independent set in G, where a subset S of the vertex set V(G) is independent if no two vertices in S are adjacent in G. The clique covering number of G, denoted $\\Theta (G)$, is the minimum number of complete subgraphs required to cover the vertices of G.","abstract_html":"We consider optimization problems on combinatorial structures with a product form. The independence number of a graph G, denoted <span class=\"etd-inline-math\">&alpha; (G)</span>, is the size of the largest independent set in G, where a subset S of the vertex set V(G) is independent if no two vertices in S are adjacent in G. The clique covering number of G, denoted $\\Theta (G)$, is the minimum number of complete subgraphs required to cover the vertices of G.","abstract_has_math":true,"creators":["Chappell, Glenn G."],"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":2011,"date_issued":"2011-05-07T13:54:37Z","date_published":"2011-05-07T13:54:37Z","updated_at":"2026-07-22T22:25:20Z","subjects":["Mathematics"],"languages":["eng"],"rights":["Copyright 1996 Chappell, Glenn G."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["9780591197617","AAI9712220","(UMI)AAI9712220"],"render_values":[{"text":"9780591197617","href":null,"code":true},{"text":"AAI9712220","href":null,"code":true},{"text":"(UMI)AAI9712220","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22881","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":["Chappell, Glenn G."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:54:37Z","2012-04-13T01:20:22Z","1996"]},{"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"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1996 Chappell, Glenn G."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["9780591197617","AAI9712220","(UMI)AAI9712220","http://hdl.handle.net/2142/22881"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We consider optimization problems on combinatorial structures with a product form. The independence number of a graph G, denoted $\\alpha (G)$, is the size of the largest independent set in G, where a subset S of the vertex set V(G) is independent if no two vertices in S are adjacent in G. The clique covering number of G, denoted $\\Theta (G)$, is the minimum number of complete subgraphs required to cover the vertices of G.","The Cartesian product of graphs G and H, denoted $G\\square H$, is defined by $V(G\\square H) = V(G)\\times V(H)$, with vertices $(g\\sb1,\\ h\\sb1)$ and $(g\\sb2,\\ h\\sb2)$ adjacent in $G\\square H$ if and only if either (1) $g\\sb1,\\ g\\sb2$ are adjacent in G and $h\\sb1 = h\\sb2$, or (2) $g\\sb1 = g\\sb2$ and $h\\sb1,\\ h\\sb2$ are adjacent in H. We seek sufficient conditions on graphs G and H for $\\alpha (G\\square H) = \\Theta (G\\square H)$.","We define product perfection, a product generalization of graph perfection. We prove product perfection for several classes of Cartesian product graphs. We extend these ideas to the context of integer linear programs. We define and study a product generalization of total dual integrality, a condition guaranteeing that a linear program has an integer optimum solution.","We also discuss optimization on product structures in the context of independence systems. An independence system is a pair consisting of a set E and a nonempty collection of subsets of E that is closed under taking subsets. We extend results of West and Tovey on products of partially ordered sets to independence systems.","A theorem of Greene and Kleitman states that in any finite partially ordered set P, certain upper bounds on the sizes of unions of antichains are tight. We extend results of West showing when the Greene-Kleitman Theorem is best possible.","Made available in DSpace on 2011-05-07T13:54:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9712220.pdf: 3476372 bytes, checksum: 24c3a554e7b5fa5f07c97665cef6552f (MD5) Previous issue date: 1996","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:00:39Z Item is restricted indefinitely.","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-04-13T01:20:22Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 9712220.pdf.txt: 142360 bytes, checksum: c7468435df9976077604d8b80a8d11d5 (MD5) license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9712220.pdf: 3476372 bytes, checksum: 24c3a554e7b5fa5f07c97665cef6552f (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-04-13T01:20:22Z"]},{"key":"dc:title","label":"Title","values":["Optimization on products of combinatorial structures"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B."],"dc:creator":["Chappell, Glenn G."],"dc:date":["2011-05-07T13:54:37Z","2012-04-13T01:20:22Z","1996"],"dc:description":["We consider optimization problems on combinatorial structures with a product form. The independence number of a graph G, denoted $\\alpha (G)$, is the size of the largest independent set in G, where a subset S of the vertex set V(G) is independent if no two vertices in S are adjacent in G. The clique covering number of G, denoted $\\Theta (G)$, is the minimum number of complete subgraphs required to cover the vertices of G.","The Cartesian product of graphs G and H, denoted $G\\square H$, is defined by $V(G\\square H) = V(G)\\times V(H)$, with vertices $(g\\sb1,\\ h\\sb1)$ and $(g\\sb2,\\ h\\sb2)$ adjacent in $G\\square H$ if and only if either (1) $g\\sb1,\\ g\\sb2$ are adjacent in G and $h\\sb1 = h\\sb2$, or (2) $g\\sb1 = g\\sb2$ and $h\\sb1,\\ h\\sb2$ are adjacent in H. We seek sufficient conditions on graphs G and H for $\\alpha (G\\square H) = \\Theta (G\\square H)$.","We define product perfection, a product generalization of graph perfection. We prove product perfection for several classes of Cartesian product graphs. We extend these ideas to the context of integer linear programs. We define and study a product generalization of total dual integrality, a condition guaranteeing that a linear program has an integer optimum solution.","We also discuss optimization on product structures in the context of independence systems. An independence system is a pair consisting of a set E and a nonempty collection of subsets of E that is closed under taking subsets. We extend results of West and Tovey on products of partially ordered sets to independence systems.","A theorem of Greene and Kleitman states that in any finite partially ordered set P, certain upper bounds on the sizes of unions of antichains are tight. We extend results of West showing when the Greene-Kleitman Theorem is best possible.","Made available in DSpace on 2011-05-07T13:54:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9712220.pdf: 3476372 bytes, checksum: 24c3a554e7b5fa5f07c97665cef6552f (MD5) Previous issue date: 1996","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:00:39Z Item is restricted indefinitely.","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2012-04-13T01:20:22Z Item was in collections: University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 9712220.pdf.txt: 142360 bytes, checksum: c7468435df9976077604d8b80a8d11d5 (MD5) license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9712220.pdf: 3476372 bytes, checksum: 24c3a554e7b5fa5f07c97665cef6552f (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2012-04-13T01:20:22Z"],"dc:identifier":["9780591197617","AAI9712220","(UMI)AAI9712220","http://hdl.handle.net/2142/22881"],"dc:language":["eng"],"dc:rights":["Copyright 1996 Chappell, Glenn G."],"dc:subject":["Mathematics"],"dc:title":["Optimization on products of combinatorial structures"],"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:25:20Z"}