Generalising separating families of fixed size

Abstract

We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set $X$ of $n$ elements we want to identify an unknown subset $Y\subset X$ of exactly $d$ elements by testing, by as few as possible subsets $A$ of $X$, whether $A$ contains an element of $Y$ or not. We are primarily concerned with the model where the family of test sets is specified in advance (non-adaptive) and each test set is of size at most a given $k$. Our main results are asymptotically sharp bounds on the minimum number of tests necessary for fixed $d$ and $k$ and for $n$ tending to infinity.

Cited by in corpus (1)

• Conscious and controlling elements in combinatorial group testing problems with more defectives