3
$\begingroup$

Related to the Union-closed sets conjecture.

Let $\phi$ be a co-HORNSAT on variables $x_1 \ldots x_n$ in CNF format. This means in every close at most one literal is negative.

The solutions of $\phi$ are closed under disjunction, which is related to set union.

Map the $j$-th solution $y_1 \ldots y_n$ to a set $S_j$, $i \in S_j$ iff $y_i$ is True.

The inverse map is $y_i \iff (i \in S_j)$.

The sets $S_j$ corresponding to the solutions of $\phi$ are closed under union, so Frankl's conjectures implies in $\phi$ there is variable $x_i$ which is True in at least half the solutions.

Is the converse true: to every union-closed family of sets $S_i$ corresponds a co-HORNSAT formula whose solutions are the mapped $S_i$?

From certain co-HORNSAT formulae got sets in which all elements are in exactly half the sets.

The powerset might cause difficulty so either exclude it or allow clauses of the form $x \lor \lnot x$.

Improve this question
$\endgroup$
9
  • $\begingroup$ Every intersection-closed family, i.e., a closure operator, can be axiomatized by Horn formulas, and yours is just the dual. Take the conjunction of all co-Horn clauses that are valid in every $S_i$, then showing that this works is a simple exercise. $\endgroup$
    – Emil Jeřábek
    Commented Jun 13, 2014 at 10:16
  • $\begingroup$ @EmilJeřábek Thanks! Do you mean: map S_i to clause, compute the truth table and convert to CNF. Take the conjunctions. This might be not co-Horn, but some minimization must make it co-Horn? $\endgroup$
    – joro
    Commented Jun 13, 2014 at 10:28
  • $\begingroup$ I mean exactly what I wrote: take the set of all co-Horn clauses $C$ with the property that for every $i$, the assignment corresponding to the set $S_i$ satisfies $C$. I don’t quite understand what you are saying, as $S_i$ is not the solution set of a clause to begin with, but yes, you are essentially asking for a conversion of a full DNF (whose disjuncts are essentialy the sets $S_i$) with some property to a co-Horn CNF. $\endgroup$
    – Emil Jeřábek
    Commented Jun 13, 2014 at 11:19
  • $\begingroup$ Thanks, I was wrong, it is indeed DNF. I think mine will work too. $\endgroup$
    – joro
    Commented Jun 13, 2014 at 11:22
  • $\begingroup$ Knuth has a program Horncount on his webpages. I don't think he talks about union-closed set systems, but he does talk about closure operators. You might check it out: it counts those systems on a base set of six elements. $\endgroup$
    – The Masked Avenger
    Commented Jun 13, 2014 at 19:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .