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 - Funding Information:
The first author’s research was supported by Funcap ( PR2010100089.01.00/15 and 4543945/2016 ) and CNPq ( 425297/2016-0 and 310512/2015-8 ). Second author’s research was supported by Hungarian National Science Fund (OTKA) , grant PD 109537 . Third author’s research was supported by Hungarian National Science Fund (OTKA), grant NK 78439 . Fourth author’s research was supported in part by the National Science Foundation , grants DMS-0906634 and CNS-0721983 , and by the Heilbronn Fund.
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 -