Skip to main content
2 of 2
edited tags
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

Is every union-closed family of set the set of solutions of some co-HORNSAT formula?

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$.

joro
  • 25.4k
  • 10
  • 66
  • 121