# Rounds in a combinatorial search problem

arXiv: https://arxiv.org/abs/1611.10133 · HTML: https://mlsanity.com/paper/1611.10133/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [On Detecting Some Defective Items in Group Testing](https://mlsanity.com/paper/2307.04822/) (2023)

## Abstract (arXiv)

We consider the following combinatorial search problem: we are given some excellent elements of [n] and we should find at least one, asking questions of the following type: "Is there an excellent element in A subset [n]?". G.O.H. Katona proved sharp results for the number of questions needed to ask in the adaptive, non-adaptive and two-round versions of this problem. We verify a conjecture of Katona by proving that in the r-round version we need to ask rn1/r+O(1) queries for fixed r and this is sharp. We also prove bounds for the queries needed to ask if we want to find at least d excellent elements.