Erdős-Selfridge Theorem for Nonmonotone CNFs
share
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 Θ(√(2) ^k) when Maker plays last, and Ω(1.5^k) and O(r^k) when Breaker plays last, where r=(1+√(5))/2≈ 1.618 is the golden ratio.
READ FULL TEXT
