Identifying defective sets using queries of small size

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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)143-150
Number of pages8
JournalDiscrete Mathematics
Volume341
Issue number1
DOIs
StatePublished - Jan 2018

Keywords

  • Combinatorial search
  • Group testing
  • Separable hypergraphs
  • Union-free hypergraphs

Fingerprint

Dive into the research topics of 'Identifying defective sets using queries of small size'. Together they form a unique fingerprint.

Cite this