Trivial two-stage group testing for complexes using almost disjunct matrices

AbstractLet [t] represent a finite population with t elements. Suppose we have an unknown d-family of k-subsets Γ of [t]. We refer to Γ as the set of positive k-complexes. In the group testing for complexes problem, Γ must be identified by performing 0, 1 tests on subsets or pools of [t]. A pool is said to be positive if it completely contains a complex; otherwise the pool is said to be negative. In classical group testing, each member of Γ is a singleton. In this paper, we exhibit and analyze a probabilistic trivial two-stage algorithm that identifies the positive complexes