Rank inequalities and separation algorithms for packing designs and sparse triple systems

AbstractCombinatorial 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, Universität Berlin, 1995; Zehendner, Doctoral Thesis, Universität Augsburg, 1986). In this article, we study polytopes associated with t-(v,k,λ) 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⩾4, the l-sparseness inequalities with 2⩽l⩽m are proven to induce facets for the m-sparse PSTS polytope; this proof uses extremal families of PSTSs known as Erdös 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(v),v⩽16. An upper bound on the size of m-sparse PSTSs is presented