Combinatorial designs find numerous applications in computer science, and are closely related to problems in coding theory. Packing designs correspond to codes with constant weight; 4-sparse partial Steiner triple systems (4-sparse PSTSs) correspond to erasure-resilient codes that are useful in handling failures in large disk arrays (Chee, Colbourn, Ling, Discrete Appl. Math., to appear; Hellerstein, Gibson, Karp, Katz, Paterson, Algorithmica 12 (1994) 182-208). The study of polytopes associated with combinatorial problems has proven to be important for both algorithms and theory, but only recently the study of design polytopes has been pursued (Moura, Math. Appl. 368 (1996) 227-254; Moura, Ph.D. Thesis, University of Toronto, 1999; Moura, Proc. Seventh Annu. European Symp. Prague, 1999, Lecture Notes in Computer Science, vol. 1643, Springer, Berlin, 1999, pp. 462-475; Wengrzik, Master's Thesis, Universitat Berlin, 1995; Zehendner, Doctoral Thesis, Universitat Augsburg, 1986). In this article, we study polytopes associated with t-(nu, k, lambda) packing designs and with m-sparse PSTSs. Subpacking and l-sparseness inequalities are introduced and studied. They can be regarded as rank inequalities for the independence systems associated with these designs. Conditions under which subpacking inequalities define facets are derived; in particular, those which define facets for PSTSs are determined. For M greater than or equal to 4, the l-sparseness inequalities with 2 less than or equal to l less than or equal to m are proven to induce facets for the m-sparse PSTS polytope; this proof uses extremal families of PSTSs known as Erdos configurations. Separation algorithms for these inequalities are proposed. We incorporate some of the sparseness inequalities in a polyhedral algorithm, and determine maximal 4-sparse PSTS(nu), nu less than or equal to 16. An upper bound on the size of m-sparse PSTSs is presented. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 25]
展开▼
