pith. sign in

arxiv: 1611.10133 · v1 · pith:D3PRXBSCnew · submitted 2016-11-30 · 🧮 math.CO · cs.DS

Rounds in a combinatorial search problem

classification 🧮 math.CO cs.DS
keywords excellentproblemcombinatorialelementsfindfollowingkatonaleast
0
0 comments X
read the original abstract

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 $rn^{1/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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.