Files in this item
Files  Description  Format 

application/pdf 9712220.pdf (3MB)  (no description provided) 
Description
Title:  Optimization on products of combinatorial structures 
Author(s):  Chappell, Glenn G. 
Doctoral Committee Chair(s):  West, Douglas B. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
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. 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 GreeneKleitman Theorem is best possible. 
Issue Date:  1996 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/22881 
ISBN:  9780591197617 
Rights Information:  Copyright 1996 Chappell, Glenn G. 
Date Available in IDEALS:  20120413 
Identifier in Online Catalog:  AAI9712220 
OCLC Identifier:  (UMI)AAI9712220 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois