1. Erd\H{o}s-Selfridge Theorem for Nonmonotone CNFs
- Author
-
Rahman, Md Lutfar and Watson, Thomas
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Data Structures and Algorithms - Abstract
In an influential paper, Erd\H{o}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\H{o}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.
- Published
- 2022