Annals of Combinatorics 3 (1999) 95-101
Sets Pooling Designs
David C. Torney
Theoretical Biology and Biophysics, Los Alamos National Laboratory, Los Alamos, New~Mexico, 87545, USA
Received January 18, 1999
AMS Subject Classification: 05B30, 05C65, 60C05, 62K99
Abstract. Pooling designs have previously been used for the efficient identification of distinguished elements of a finite set U. Group testing underlies these designs: For any a binary result is obtainable, indicating whether or not the number of distinguished elements included in S is zero. The current generalization of pooling designs will enable the efficient identification of distinguished subsets of a finite set U. In this case, for any , a binary result is obtainable, indicating whether or not the number of distinguished subsets included in S is zero. Such designs are called sets pooling designs, comprising standard pooling designs in the special case where all the distinguished subsets are elements. The new designs are similar to the standard designs but are subject to new constraints because the set of subsets included in Sis its power set. To illustrate the feasibility of constructing sets pooling designs, random, non-adaptive designs are investigated for the special case where all distinguished subsets have the same size. An optimum probability for including an object in a pool is approximated as a function of the size and number of distinguished subsets, adopting the criterion of minimizing the average number of non-distinguished subsets whose status would not be resolved by the pooling design. Deterministic and adaptive designs are also described.
Keywords: block design, group testing, extremal sets, asymptotic approximation, positive sets