Erdős-Selfridge Theorem for Nonmonotone CNFs

Abstract

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 $\Theta (2^k)$. We study the analogous question when the CNF is not necessarily monotone. We prove bounds of $\Theta (\sqrt{2}{}^k)$ when Maker plays last, and $\Omega (1.5^k)$ and $O(r^k)$ when Breaker plays last, where $r=(1+\sqrt{5})/2\approx 1.618$ is the golden ratio.