2009/04/16 by Heidi Gebauer, Gebauer, Heidi
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Computational Geometry and Mesh Generation #Computer Science and Game Theory (cs.GT) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #G.2.1 #cs.GT
paper · pdf · doi:10.48550/arxiv.0904.2541
12 pages, 1 figure
openalex publication_date 2009/04/16 · arxiv created 2009/05/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a Maker/Breaker game described by Beck. As a result we disprove a conjecture of Beck on positional games, establish a connection between this game and SAT and construct an unsatisfiable k-CNF formula with few occurrences per variable, thereby improving a previous result by Hoory and Szeider and showing that the bound obtained from the Lovasz Local Lemma is tight up to a constant factor. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph F, with Maker going first. Maker's goal is to completely occupy a hyperedge and Breaker tries to avoid this. Beck conjectures that if the maximum neighborhood size of F is at most 2^(n-1) then Breaker has a winning strategy. We disprove this conjecture by establishing an n-uniform hypergraph with maximum neighborhood size 3*2^(n - 3) where Maker has a winning strategy. Moreover, we show how to construct an n-uniform hypergraph with maximum degree (2^(n-1))/n where maker has a winning strategy. Finally, we establish a connection between SAT and the Maker/Breaker game we study. We can use this connection to derive new results in SAT. Kratochvil, Savicky and Tuza showed that for every k >= 3 there is an integer f(k) such that every (k,f(k))-formula is satisfiable, but (k,f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvil, Savicky and Tuza also gave the best known lower bound f(k) = Omega(2k/k), which is a consequence of the Lovasz Local Lemma. We prove that, in fact, f(k) = Theta(2k/k), improving upon the best known upper bound O((log k) * 2k/k) by Hoory and Szeider.