## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, October 30, 2008, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Heidi Gebauer

## Unsatisfiable CNF-Formulas with Small Neighborhoods

By (k,s)-CNF we denote the set of CNF-formulas where every clause has exactly k distinct literals and each variable occurs in at most s clauses. Kratochvil, Savicky and Tuza showed by using the Lovasz Local Lemma that every (k, 2^k/ (ek))-CNF formula is satisfiable. From the other side Hoory and Szeider established unsatisfiable (k, log(k) * 2^k/ k)-CNF formulas, implying that the bound of Kratochvil et al. is tight up to a logarithmic factor. We can show that the bound of Kratochvil is even asymptotically tight by constructing an unsatisfiable(k, 4 * 2^k/ k)-CNF formula. This construction will be presented in the talk.

Information for students and suggested topics for student talks