Construction of a Non-2-colorable k-uniform Hypergraph with Few Edges
Gebauer, Heidi
Original · EN
We show how to construct a non-2-colorable k-uniform hypergraph with (2(1 + o(1)))ᵏ edges. By the duality of hypergraphs and monotone k-CNF-formulas this gives an unsatisfiable monotone k-CNF with (2(1 + o(1)))ᵏ clauses
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.