Note on a Conjecture for Group Testing

Abstract

Let \(M(d,n)\) denote the minimax number of group tests required for the identification of the \(d\) defectives in a set of \(n\) items. It was conjectured by Hu, Hwang, and Wang that \(M(d,n) = n-1\) for \(n \leq 3d\), a surprisingly difficult combinatorial problem with very little known. The best known result is \(M(d,n) = n-1\) for \(n \leq \frac{42}{16}d\) by Du and Hwang. In this note, we improve their result by proving \(M(d,n) = n – 1\) for \(d \geq 193\) and \(n \leq \frac{42}{16}d\).