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\le 3d$, a surprisingly difficult combinatorial problem with very little known. The best known result is $M(d,n)=n-1$ for $n\le \frac{42}{16}d$ by Du and Hwang. In this note, we improve their result by proving $M(d,n)=n–1$ for $d\ge 193$ and $n\le \frac{42}{16}d$.