TY - JOUR

T1 - Identifying defective sets using queries of small size

AU - Benevides, Fabrício S.

AU - Gerbner, Dániel

AU - Palmer, Cory T.

AU - Vu, Dominik K.

N1 - Publisher Copyright:
© 2017 Elsevier B.V.

PY - 2018/1

Y1 - 2018/1

N2 - 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 of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.

AB - 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 of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.

KW - Combinatorial search

KW - Group testing

KW - Separable hypergraphs

KW - Union-free hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=85029163841&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2017.08.023

DO - 10.1016/j.disc.2017.08.023

M3 - Article

AN - SCOPUS:85029163841

SN - 0012-365X

VL - 341

SP - 143

EP - 150

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -