Generalising separating families of fixed size
classification
🧮 math.CO
keywords
elementsfixedgivensizesubsettestadvanceasymptotically
read the original 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 $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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.