Disproof of the neighborhood conjecture with implications to SAT

DOI10.1007/s00493-012-2679-yzbMath1289.68047OpenAlexW1782236248WikidataQ123017151 ScholiaQ123017151MaRDI QIDQ377802

Heidi Gebauer

Publication date: 7 November 2013

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/61671

zbMATH Keywords

binary treeSAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Positional games (pursuit and evasion, etc.) (91A24) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Unsplittable coverings in the plane ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ On the parameterized complexity of \((k,s)\)-SAT ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma

Cites Work

• Unnamed Item
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• Lopsided Lovász Local lemma and Latin transversals
• A simplified NP-complete satisfiability problem
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• On the structure of some classes of minimal unsatisfiable formulas
• Homomorphisms of conjunctive normal forms.
• DNF tautologies with a limited number of occurrences of every variable
• Unsatisfiable Linear CNF Formulas Are Large and Complex.
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• Remarks on positional games. I
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• A constructive proof of the Lovász local lemma
• Combinatorial Games
• On a combinatorial game

This page was built for publication: Disproof of the neighborhood conjecture with implications to SAT