Generalising separating families of fixed size

MaRDI QIDQ6265028zbMATH OpenFDO

Authors F. S. Benevides, Dániel Gerbner, Cory Palmer, Dominik K. Vu

Publication date 1 September 2015

Abstract: We examine the following version of a classic combinatorial search problem introduced by R'enyi: Given a finite set $X$ of $n$ elements we want to identify an unknown subset $YsubsetX$ 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.

This page was built for publication: Generalising separating families of fixed size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6265028)