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 able to correct all (except for "bad ones") 4-erasures, which are useful in handling failures in large disk arrays (4, 10). The study of poly-topes associated with combinatorial problems has proven to be important for both algorithms and theory. However, research on polytopes for problems in combinatorial design and coding theories have bene pursued only recently (14, 15, 17, 20, 21), In this article, polytopes asosciated with t-(v, k, lambda) packing designs and sparse PSTSs are studied. The subpacking and sparseness inequalities are introduced. These can be regarded as rank inequalities for the independence systems associated with these deisgns. Conditions under which subpacking inequalities define facets are studies. Sparsencess inequalities are proven to induce facets for the sparse PSTS polytope; some extremal families of PSTS known as Erdos configuraitons play a central role in this proof. The incorporation of thes eindequalities in polyhedral algorithms and their use for deriving upper bounds on the paking numbers are suggested. A sample of 4-sparse PSTS(v), v <= 16, obtained by such an algorithm is shown; an upper bound on the size of m-sparse PSTSs is presented.
展开▼
