Optimal pooling designs with error detection (Q1914001)

Given are \(n\) objects, each of them can be ``good'' or ``bad''. A test is available, which---with a small marginal possibility of error---determines whether or not all the objects in a given collection are good. (However, after the evaluation we can recognise the failed tests.) The problem is to resolve the status of each object using the minimum number of tests applied in parallel. (This type of problems have big practical influence for topics like constructing physical map of human chromosomes.) If there is an a priori upper bound \(p\) for the number \(P\) of bad objects, with probability 0 of test-failure, then we are in the well-studied ``hypergeometric'' case. In practical cases this a priori upper bound may be misleading. The paper under review throws out the a priori upper bound condition, but assumes that case \(P > p\) can be detected a posteriori. It is shown that an optimal solution is equivalent to a maximal subset system of an underlying set, such that every subset has more than \(q\) elements distinct from any union of up to \(p\) others. For that later problem Ruszinkó derived asymptotic bounds for the case \(q = 0\) (but \(p\) is arbitrary). The current paper derives lower bounds for cases \(p = 1\) and \(p = 2\) but for arbitrary \(q\)'s. It turns out that in some cases corresponding Steiner triple systems give optimal solutions.