Polyhedral aspects of combinatorial designs

grantor: University of TorontoA 't'- v,k,l 'design' is a collection of 'k'-subsets (called 'blocks') of a 'v'-set such that every ' t'-subset of the 'v'-set is contained in 'exactly ' l blocks; 't'- v,k,l 'packing designs' and 'covering designs' are defined by replacing the word 'exactly' by 'at most ' and 'at least', respectively. The polyhedron associated with a design is the convex hull of the incidence x∈Rv k of all designs of that kind. Given 's' >= 2 and 'v' >= 'k' >= t >= 1, a family A of 'k'-subsets of 1,v is said to be 's-wise t-intersecting', if any ' s' members A1,&ldots;,As of A are such that ∣ A1[intersection]&ldots;[intersection]As ∣ >=t ; Let us denote by Isv,k,t the set of all such families. The thesis is divided into three parts. In the first part, a theoretical investigation of design polytopes is undertaken. Let Tt,v,k,l and Pt,v,k,l denote the polyhedra associated with 't'- v,k,l designs and packings, respectively. Maximal clique facets for Pt,v,k,l are characterized as maximal ( l + 1)-wise 't'-intersecting families of 'k'-sets of a 'v'-set. Subpacking inequalities for Pt,v,k,l are derived and conditions under which these inequalities define facets are given. We provide 'm'-sparse facets for the 'm'-sparse 2-('v', 'k', 1) packing polytope. We also show that if the difference of two designs is a ('t', 'k ')-pod, a null design of minimum support, the designs are adjacent as vertices of the Tt,v,k,1 polytope. In the second part, we investigate the following problem: "Given ' s' >= 2, 'v' > 'k' > 't', classify all maximal (with respect to set inclusion) families in Isv,k,t ". This is a wide open problem in extremal set theory. We solve the classification problem for the first nontrivial case, namely ' s' = 2, 'k' = 't' + 2 and arbitrary ' v'. We also prove that the classification problem does not depend on 'v'. In order to derive these results, properties relating kernels and generating sets of maximal families are proven, and a construction of maximal families in Isv+1,k+ 1,t+1 based on the ones in Isv,k,t is given. The third part of the thesis focuses on polyhedral algorithms for constructing ' t'-('v', 'k', 1) designs and packings, and 'm'-sparse triple systems with 'm' = 4, 5. A branch-and-cut algorithm is proposed and an implementation is described. Separation algorithms for cliques and 'm'-sparse inequalities are presented. A partial isomorph rejection scheme is employed to avoid processing isomorphic subproblems in the branch-and-cut tree. The effects of various parameters on performance are analyzed through experiments. Our method is competitive with many other techniques for generating designs including backtracking and randomized search. Our algorithm produces new maximal cyclic ' t'-('v', 'k', 1) packings for ' t' = 2, 3, 4, 5, 'k' = 't' + 1, ' t' + 2 and small 'v'.Ph.D