Rounds in Combinatorial Search

Gábor Wiener

ABSTRACT: A set system H &sube 2^[m] is said to be separating if for every pair of distinct elements x,y &isin [m] there exists a set H &isinH such that H contains exactly one of them. The search complexity of a separating system H &sube 2^[m] is the minimum number of questions of type "x&isinH?" (where H&isinH) needed in the worst case to determine a hidden element x&isin[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by c(H), if the questions are all fixed beforehand, then we speak of the non-adaptive complexity, denoted by c_na(H). If we are allowed to ask the questions in at most k batches then we speak of the k-round complexity of H, denoted by c_k(H). It is clear that |H|&ge c_na(H) &ge c₁(H) &ge c₂(H) ... &ge c_m(H) =c(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 the lecture we are discussing set systems H with the property |H|=c_k(H) for any k&ge 3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.