An efficient search strategy for hidden ideals in pointed partially ordered sets

Abstract

We consider a combinatorial question about searching for an unknown ideal $\hat{I}¼$ within a known pointed poset $\hat{I}»$. Elements of $\hat{I}»$ may be queried for membership in $\hat{I}¼$, but at most $k$ positive queries are permitted. We provide a general search strategy for this problem, and establish new bounds (based on $k$ and the degree and height of $\hat{I}»$) for the total number of queries required to identify $\hat{I}¼$. We show that this strategy performs asymptotically optimally on the family of complete $\ell$-ary trees as the height grows.