Document Type
Lecture
Publication Date
11-5-2014
Abstract
Given an n-element set which contains a known number d of unknown special elements, we are allowed to use an oracle which accepts queries of size k and responds positively if at least one of the elements of the queried set is in our set of unknowns. The case of a single unknown element has been studied and solved in the past by Rnyi (1961), Katona (1966) and more recently by Hosszu, Tapolcai and Wiener (2013). We generalise their results in both the adaptive (on-line) and non-adaptive (parallelised) case for general d. Our approach provides new links between separability and (hyper-)graph girth, as well as new bounds for the problem. This is joint work with F. Benevides, D. Gerbner and C. Palmer.
Relational Format
presentation
Recommended Citation
Vu, Dominik, "Combinatorial search and separating families" (2014). Combinatorics Seminar. 46.
https://egrove.olemiss.edu/math_combinatorics/46
