Construction of a Non-2-colorable k-uniform Hypergraph with Few Edges
classification
💻 cs.DM
keywords
edgeshypergraphk-uniformmonotonenon-2-colorableclausesconstructconstruction
read the original abstract
We show how to construct a non-2-colorable k-uniform hypergraph with (2^(1 + o(1)))^k edges. By the duality of hypergraphs and monotone k-CNF-formulas this gives an unsatisfiable monotone k-CNF with (2^(1 + o(1)))^k clauses
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.