Generalising separating families of fixed size

2015/09/01 by Fabrício S. Benevides, Dániel Gerbner, Benevides, Fabrício S. +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1509.00131

arxiv created 2015/09/01 · arxiv updated 2015/09/02

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 ⊂ 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.

Related

• Smart elements in combinatorial group testing problems
• Group Testing with Pools of Fixed Size
• Lower bounds for identifying subset members with subset queries
• Computationally Tractable Algorithms for Finding a Subset of Non-defective Items from a Large Population
• Constraining the Number of Positive Responses in Adaptive, Non-Adaptive, and Two-Stage Group Testing