Erdős-Selfridge Theorem for Nonmonotone CNFs

In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker's goal is to satisfy the CNF, while Maker's goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with $k$ literals per clause where Maker has a winning strategy is $Θ(2^k)$. We study the analogous question when the CNF is not necessarily monotone. We prove bounds of $Θ(\sqrt{2}\,^k)$ when Maker plays last, and $Ω(1.5^k)$ and $O(r^k)$ when Breaker plays last, where $r=(1+\sqrt{5})/2\approx 1.618$ is the golden ratio.

No reviews yet.

No comments yet.