Based on comments on MO there is simple forumlation of Frankl's union-closed sets conjecture in terms of (co-)Horn.

In co-Horn CNF at most one literal is negated in every clause (Horn CNF where every literal is negated).

Frankl's union-closed sets conjecture is equivalent to the following:

(A) Let $\phi$ be Horn (resp co-Horn) formula in CNF in variables $x_1 \ldots x_n$ with more than one solution. There is a variable $x_i$ which is False (resp True) in at least half the solutions.

  1. Are there sufficient conditions $\phi$ to satisfy (A)?
  2. How would a minimal counterexample look like?

My guess about (2) is that one must maximize the positive (resp negative) literals and all clauses will be binary of the form $x \lor \lnot y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.