Disproof of the neighborhood conjecture with implications to SAT
Disproof of the neighborhood conjecture with implications to SAT
复制标题
反驳邻域猜想对 SAT 的影响
作者：
Heidi Gebauer
我们研究了一类特殊的二叉树。我们的结果对Maker/Breaker游戏和SAT有启示：我们反驳了Beck关于位置游戏的一个猜想，并构造了一个每个变量很少出现的不可满足的k-CNF公式，从而改进了Hoory和Szeider先前的结果，并表明从Lovász局部引理获得的界紧绷到一个常数因子。A (k, s)-CNF公式是合取范式的布尔公式，其中每个子句恰好包含k个不同的字面值，每个变量最多出现在s个子句中。（k, s）-SAT问题是限定于(k, s)-CNF公式的可满足性问题。Kratochvíl， Savický和Tuza表明，对于每一个k≥3，存在一个整数f(k)，使得每一个(k, f(k))-CNF公式都是可满足的，但(k, f(k) + 1)-SAT已经是np完全的（不知道f(k)是否可计算）。Kratochvíl， Savický和Tuza也给出了最著名的下限文档类[12pt]最小usepackageamsmath useppackagewasysym useppackageamsfonts useppackageamssymb useppackageamssy useppackagemathrsfs useppackageupgreek setlengthoddsidemargin-69pt egindocument {}{}{}{}{}{}{}{}{}{}{}$$f(k) = Omega left( { frac{{2^k }} {k}}
ight)$$ enddocument，这是Lovász本地引论的结果。我们证明了，实际上，documentclass[12pt]minimal usepackageamsmath useppackageamsfonts useppackageamssymb useppackageamssy useppackageamsfs setlengththoddsidemargin -69pt egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$f(k) = Theta left( { frac{{2^k }} {k}}
ight)$$ enddocument，改进了最著名的上界documentclass[12pt]minimal usepackageamsmath useppackageamsfonts useppackageamssymb useppackageamssyb useppackagemathrsfs useppackageupgreek setlengththoddsidemargin -69pt egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$Oleft( {(log k) cdot frac{{2^k }} {k}}
ight)$$ enddocument由Hoory和Szeider。最后，我们建立了我们所考虑的一类树与一类特定的位置对策之间的联系。我们研究的Maker/Breaker游戏如下。Maker和Breaker轮流从给定的n-uniform超图documentclass[12pt]minimal uspackageamsmath uspackagewasysym uspackageamsfonts uspackageamssymb uspackageamssyb uspackagagemathrsfs uspackageupgreek setlengthoddsidemargin-69pt egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$mathcal{F}$$ enddocument中选择顶点，Maker先选择。Maker的目标是完全占领一个超级边缘，而Breaker试图阻止这一点。超图的最大邻接大小documentclass[12pt]minimal useppackageamsmath useppackageamsfonts useppackageamssyb useppackageamssyb useppackageamssyb useppackageamssyb useppackageamsfonts useppackageamssyb useppackageamssyb useppackageamssyb useppackagemathrss useppackageams希腊setlengthoddsidmargin -69pt egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$mathcal{F}$$ enddocument是最大的s，这样一些超图的documentclass[12pt]minimal useppackageamsmath uspackagewasysym useppackageamssb useppackageamssyb useppackagemathrss useppackageams希腊setlengthoddsidmargin -69ptegindocument {}{}{}{}{}{}{}{}{}{}{}{}$$mathcal{F}$$ enddocument正好与其他5条超边相交。Beck推测，如果documentclass的最大邻域大小[12pt]minimal usepackageamsmath useppackagewasysym useppackageamsfonts useppackageamssymb useppackageamssyb useppackageamssfs useppackageupgreek setlengthoddsidemargin-69pt egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$mathcal{F}$$ enddocument小于2n−1−1，则Breaker具有获胜策略。我们通过证明，对于每一个n≥3，存在一个最大邻域大小为3·2n−3的n-均匀超图，其中Maker具有一个制胜策略来反驳这一猜想。此外，我们还展示了如何为每个n构造一个n-均匀的超图，其最大度最多为documentclass[12pt]。最小的usepackageamsmath。useppackageamsfonts。useppackageamssymb。useppackageamssyb。useppackageamsfs。useppackageams希腊。setlengthoddsidemargin-69pt 。egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$frac{{2^{n + 2} }} {n}$$。此外，我们还证明了每个n-均匀超图的最大度最多为documentclass[12pt]最小usepackageamsmath useppackagewasysym useppackageamsfonts useppackageamssymb useppackageamssy useppackageamsfs useppackageupgreek setlengthoddsidemargin-69pt egindocument {}{}{}{}{}{}{}{}{}{}{}{}$$frac{{2^{n - 2} }} {{en}}$$ enddocument具有适当的一半2-上色，这解决了Beck提出的与邻域猜想相关的另一个开放问题。{}
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 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$f(k) = Omega left( { frac{{2^k }} {k}}
ight)$$ end{document}, which is a consequence of the Lovász Local Lemma. We prove that, in fact, documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$f(k) = Theta left( { frac{{2^k }} {k}}
ight)$$ end{document}, improving upon the best known upper bound documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$Oleft( {(log k) cdot frac{{2^k }} {k}}
ight)$$ end{document} 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 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$mathcal{F}$$ end{document}, 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 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$mathcal{F}$$ end{document} is the maximal s such that some hyperedge of documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$mathcal{F}$$ end{document} intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$mathcal{F}$$ end{document} 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 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$frac{{2^{n + 2} }} {n}$$ end{document} where Maker has a winning strategy. In addition we show that each n-uniform hypergraph with maximum degree at most documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document} $$frac{{2^{n - 2} }} {{en}}$$ end{document} has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.