A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Michal Koucký, Vojtěch Rödl, Navid Talebanfard

We show that for every $r\ge 2$ there exists ${\epsilon }_r>0$ such that any $r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$ contains a set of at most $(\fra…