Identifying defective sets using queries of small size

Fabrício S. Benevides; Dániel Gerbner; Cory T. Palmer; Dominik K. Vu

doi:10.1016/j.disc.2017.08.023

Identifying defective sets using queries of small size

Fabrício S. Benevides
, Dániel Gerbner
, Cory T. Palmer
, Dominik K. Vu

Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	143-150
Number of pages	8
Journal	Discrete Mathematics
Volume	341
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2017.08.023
State	Published - Jan 2018

Funding

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.

Funders	Funder number
CNS-0721983, DMS-0906634
NK 78439, PD 109537
Conselho Nacional de Desenvolvimento Científico e Tecnológico	425297/2016-0, 310512/2015-8

Keywords

Combinatorial search
Group testing
Separable hypergraphs
Union-free hypergraphs

Access to Document

10.1016/j.disc.2017.08.023

Cite this

@article{3213a2c745f54e0a883852fbf797dda1,

title = "Identifying defective sets using queries of small size",

abstract = "We examine the following version of a classic combinatorial search problem introduced by R{\'e}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.",

keywords = "Combinatorial search, Group testing, Separable hypergraphs, Union-free hypergraphs",

author = "Benevides, \{Fabr{\'i}cio S.\} and D{\'a}niel Gerbner and Palmer, \{Cory T.\} and Vu, \{Dominik K.\}",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2018",

month = jan,

doi = "10.1016/j.disc.2017.08.023",

language = "English",

volume = "341",

pages = "143--150",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

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.

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 - https://www.scopus.com/pages/publications/85029163841

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 -

Identifying defective sets using queries of small size

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this