A GROUP-TESTING PROBLEM FOR HYPERGRAPHS OF BOUNDED RANK

Suppose that a hypergraph H = (V,E) of rank r is given as well as a pr obability distribution p(e) (e is an element of E) on the edges. We sh ow that in the usual group testing model the unknown edge can be found by less than - log p(e) + r tests. For the case of the uniform distri bution, the result proves a conjecture of Du and Hwang.