mlsanityData to 14 Oct 2026

Rounds in a combinatorial search problem

arXiv 1611.10133 ↗First posted 30 Nov 2016math.CO cs.DScited by 1

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2023: 1.

1 paper.