Computer Science > Computer Science and Game Theory
[Submitted on 16 Apr 2009 (v1), last revised 15 May 2009 (this version, v3)]
Title:Disproof of the Neighborhood Conjecture with Implications to SAT
View PDFAbstract: 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(2^k/k), which is a consequence of the Lovasz Local Lemma. We prove that, in fact, f(k) = Theta(2^k/k), improving upon the best known upper bound O((log k) * 2^k/k) by Hoory and Szeider.
Submission history
From: Heidi Gebauer [view email][v1] Thu, 16 Apr 2009 17:04:21 UTC (37 KB)
[v2] Thu, 7 May 2009 21:25:14 UTC (37 KB)
[v3] Fri, 15 May 2009 07:59:53 UTC (38 KB)
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
Connected Papers (What is Connected Papers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.