๐ฎ
๐ฎ
The Ethereal
Rounds in a combinatorial search problem
November 30, 2016 ยท The Ethereal ยท ๐ Discrete Applied Mathematics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Dรกniel Gerbner, Mรกtรฉ Vizer
arXiv ID
1611.10133
Category
math.CO: Combinatorics
Cross-listed
cs.DS
Citations
7
Venue
Discrete Applied Mathematics
Last Checked
2 months ago
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.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal