Timeline for Is every union-closed family of set the set of solutions of some co-HORNSAT formula?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2014 at 3:01 | review | Close votes | |||
| Jun 25, 2014 at 1:19 | |||||
| Jun 15, 2014 at 4:33 | comment | added | joro | @TheMaskedAvenger Thanks. Horn gives set intersection which is equivalent. Your example leads to the empty set IMHO and this is excluded in Frankl's (missed this in the OP). | |
| Jun 15, 2014 at 3:39 | history | edited | Andrés E. Caicedo |
edited tags
|
|
| Jun 15, 2014 at 0:40 | comment | added | The Masked Avenger | If you mean a representation of a (non-Frankl) union closed finite set family encoded as a conjunction of Horn clauses, the only example I know of is TRUE (or maybe I mean FALSE). | |
| Jun 14, 2014 at 6:52 | comment | added | joro | @TheMaskedAvenger thanks. In terms of coHorn how a minimal counterexample would look like? I suspect one must maximize the negative literals, so this would mean all clauses are binary with one negative literal. | |
| Jun 13, 2014 at 19:24 | comment | added | The Masked Avenger | There is also oeis.org/A102897 if you want the enumeration sequence. | |
| Jun 13, 2014 at 19:22 | comment | added | The Masked Avenger | 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. | |
| Jun 13, 2014 at 11:22 | comment | added | joro | Thanks, I was wrong, it is indeed DNF. I think mine will work too. | |
| Jun 13, 2014 at 11:19 | comment | added | Emil Jeřábek | 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. | |
| Jun 13, 2014 at 10:33 | review | Close votes | |||
| Jun 13, 2014 at 11:19 | |||||
| Jun 13, 2014 at 10:28 | comment | added | joro | @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? | |
| Jun 13, 2014 at 10:16 | comment | added | Emil Jeřábek | 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. | |
| Jun 13, 2014 at 9:46 | history | asked | joro | CC BY-SA 3.0 |