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 $Hinmathcal{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 inmathcal{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}| geqmathrm{c}_{na} (mathcal{H}) = mathrm{c}_{1} (mathcal{H}) geqmathrm{c}_{2} (mathcal{H}) geqcdotsgeqmathrm{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.