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