pith. sign in

arxiv: 1509.00131 · v1 · pith:7H4CPE4Znew · submitted 2015-09-01 · 🧮 math.CO

Generalising separating families of fixed size

classification 🧮 math.CO
keywords elementsfixedgivensizesubsettestadvanceasymptotically
0
0 comments X
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.