Rounds in Combinatorial Search
A set system \(\mathcal{H} \subseteq2^{[m]}\) is said to be separating if for every pair of distinct elements x,y?[m] there exists a set \(H\in\mathcal{H}\) such that H contains exactly one of them. The search complexity of a separating system \(\mathcal{H} \subseteq 2^{[m]}\) is the minimum number of questions of type x?H? (where \(H \in\mathcal{H}\)) needed in the worst case to determine a hidden element x?[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by \(\mathrm{c} (\mathcal{H})\); if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by \(\mathrm{c}_{na} (\mathcal{H})\). If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of \(\mathcal{H}\), denoted by \(\mathrm{c}_{k} (\mathcal{H})\). It is clear that \(|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})\). A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems \(\mathcal{H}\) with the property \(|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) \) for any k?3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.
rounds search adaptivity group testing