An extension of Stein-Lovasz theorem and some of its applications

Abstract

The Stein-Lovasz theorem provides an algorithmic way to deal with the existence of certain good coverings, and thus offers bounds related to some combinatorial structures. An extension of the classical Stein-Lovasz theorem for multiple coverings is given, followed by some applications for finding upper bounds of the sizes of (d,s out of r;z]-disjunct matrices and (k,m,c,n;z)-selectors, respectively. This gives a unified treatment for some previously known results relating to various models of group testing.