期刊
COMBINATORICA
卷 32, 期 5, 页码 573-587出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s00493-012-2679-y
关键词
-
类别
资金
- SNF [200021-118001/1]
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 Lovasz 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. Kratochvil, SavickA1/2 and Tuza showed that for every ka parts per thousand yen3 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). Kratochvil, SavickA1/2 and Tuza also gave the best known lower bound , which is a consequence of the Lovasz Local Lemma. We prove that, in fact, , improving upon the best known upper bound 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 , 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 is the maximal s such that some hyperedge of intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of is smaller than 2 (n-1) - 1 then Breaker has a winning strategy. We disprove this conjecture by establishing, for every na parts per thousand yen3, the existence of an n-uniform hypergraph with maximum neighborhood size 3 center dot 2 (n-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 where Maker has a winning strategy. In addition we show that each n-uniform hypergraph with maximum degree at most has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据