Searching for quicksand ideals in partially ordered sets

Abstract

We consider a combinatorial question about searching for an unknown ideal $\mu$ within a known poset $\lambda$. Elements of $\lambda$ may be queried for membership in $\mu$, but at most $k$ positive query results are permitted. The goal is to find a search strategy which guarantees a solution in a minimal total number $m_k(\lambda )$ of queries. We provide tight bounds for $m_k(\lambda )$, and construct optimal search strategies for the case where $k=2$ and $\lambda$ is the product poset of totally ordered finite sets, one of which has cardinality not more than six.