Abstract
We study a special class of binary trees. Our results have implications on Maker/Breaker games and SAT: We disprove a conjecture of Beck on positional games 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 Lovász Local Lemma is tight up to a constant factor.
A (k, s)-CNF formula is a boolean formula in conjunctive normal form where every clause contains exactly k distinct literals and every variable occurs in at most s clauses. The (k, s)-SAT problem is the satisfiability problem restricted to (k, s)-CNF formulas. Kratochvíl, Savický and Tuza showed that for every k≥3 there is an integer f(k) such that every (k, f(k))-CNF formula is satisfiable, but (k, f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvíl, Savický and Tuza also gave the best known lower bound \(f(k) = \Omega \left( {\tfrac{{2^k }} {k}} \right)\), which is a consequence of the Lovász Local Lemma. We prove that, in fact, \(f(k) = \Theta \left( {\tfrac{{2^k }} {k}} \right)\), improving upon the best known upper bound \(O\left( {(\log k) \cdot \tfrac{{2^k }} {k}} \right)\) by Hoory and Szeider.
Finally we establish a connection between the class of trees we consider and a certain family of positional games. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph \(\mathcal{F}\), with Maker going first. Maker’s goal is to completely occupy a hyperedge and Breaker tries to prevent this. The maximum neighborhood size of a hypergraph \(\mathcal{F}\) is the maximal s such that some hyperedge of \(\mathcal{F}\) intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of \(\mathcal{F}\) is smaller than 2n−1 − 1 then Breaker has a winning strategy. We disprove this conjecture by establishing, for every n≥3, the existence of an n-uniform hypergraph with maximum neighborhood size 3·2n−3 where Maker has a winning strategy. Moreover, we show how to construct, for every n, an n-uniform hypergraph with maximum degree at most \(\frac{{2^{n + 2} }} {n}\) where Maker has a winning strategy.
In addition we show that each n-uniform hypergraph with maximum degree at most \(\frac{{2^{n - 2} }} {{en}}\) has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. Aharoni and N. Linial: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas, J. Combin. Theory Ser. A 43, (1986), 196–204.
N. Alon and J. H. Spencer: The Probabilistic Method, J. John Wiley & Sons (2002).
J. Beck: Combinatorial Games: Tic Tac Toe Theory, Encyclopedia of Mathematics and its Applications 114, 2008.
J. Beck: Remarks on positional games, Acta Math. Acad. Sci. Hungar. 40, (1982), 65–71.
G. Davydov, I. Davydova and H. Kleine Büning: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF, Artif. Intell. 23, (1998), 229–245.
P. Erdős and J. L. Selfridge: On a combinatorial game, J. Combinatorial Theory Ser. A 14, (1973), 298–301.
P. Erdős and J. Spencer: Lopsided Lovász local lemma and Latin transversals, Discrete Appl. Math. 30, (1991), 151–154.
H. Gebauer, T. Szabó and G. Tardos: The Local Lemma is Tight for SAT, Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2011), 664–674.
S. Hoory and S. Szeider: A note on unsatisfiable k-CNF formulas with few occurrences per variable, SIAM J. Discrete Math 20(2), (2006), 523–528.
S. Hoory and S. Szeider: Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable, Theoretical Computer Science 337(1–3), (2005), 347–359.
H. Kleine Büning and X. Zhao: On the structure of some classes of minimal unsatisfiable formulas, Discr. Appl. Math. 130(2), (2003), 185–207.
J. Kratochvíl, P. Savický and Z. Tuza: One more occurrence of variables makes satisfiability jump from trivial to NP-complete, SIAM J. Comput. 22(1), (1993), 203–210.
O. Kullmann: An application of matroid theory to the SAT problem, Fifteenth Annual IEEE Conference on Computational Complexity, (2000), 116–124.
R. Moser: A constructive proof of the Lovász Local Lemma, Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), (2009), 343–350.
P. Savický and J. Sgall: DNF tautologies with a limited number of occurrences of every variable, Theoret. Comput. Sci. 238(1–2), (2000), 495–498.
D. Scheder: Unsatisfiable Linear CNF Formulas Are Large and Complex, 27th International Symposium on Theoretical Aspects of Computer Science (STACS), (2010), 621–631.
S. Szeider: Homomorphisms of conjunctive normal forms, Discr. Appl. Math. 130(2), (2003), 351–365.
C. A. Tovey: A simplified NP-complete satisfiability problem, Discr. Appl. Math. 8(1), (1984), 85–89.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract appeared in Proc. 17th European Symposium on Algorithms (ESA) (2009)
Research is supported by the SNF Grant 200021-118001/1.
Rights and permissions
About this article
Cite this article
Gebauer, H. Disproof of the neighborhood conjecture with implications to SAT. Combinatorica 32, 573–587 (2012). https://doi.org/10.1007/s00493-012-2679-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-012-2679-y