Horn clause formulation: Difference between revisions
TobiasFritz (talk | contribs) begin adding content |
TobiasFritz (talk | contribs) No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form | The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form | ||
<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in | <math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in A</math> | ||
To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>. | To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>. | ||
| Line 11: | Line 11: | ||
=== Maximal one === | === Maximal one === | ||
Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not | Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not an element of any <math>\mathcal{A}</math>-member contained in <math>A</math>; this is possible due to the union-closure assumption. Then put <math>S:=X\setminus A</math>. | ||
In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. | In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. The following is taken from [http://www.sciencedirect.com/science/article/pii/S0304397510000034 this paper], which investigates the dual notions for intersection-closed families. | ||
=== Using minimal transversals === | === Using minimal transversals === | ||
< | It is sufficient to consider those <math>(x,S)</math> for which <math>S</math> is not contained in any other <math>S'</math> for which <math>(x,S')</math>. In other words, <math>S</math> can be assumed to be a [https://en.wikipedia.org/wiki/Hypergraph#Transversals minimal transversal] of <math>\mathcal{A}_x</math>. | ||
Various reformulations of this can be found in the paper above. | |||
=== Using free sets === | |||
A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (At least this is the terminology used in the dual case of intersection-closed families, where it seems to be motivated by the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>. | |||
== Literature == | == Literature == | ||
For intersection-closed families, there are plenty of papers in certain areas of artificial intelligence research, including data analysis and formal concept analysis. | For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey]. | ||
[[Category:Frankl's union-closed sets conjecture]] | |||
Latest revision as of 01:50, 11 March 2016
The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form
[math]\displaystyle{ x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in A }[/math]
To keep the notation concise, we use the shorthand notation [math]\displaystyle{ (x,S) }[/math] for such a Horn clause. The following page provides various details of this formulation. Throughout, [math]\displaystyle{ \mathcal{A}\subseteq 2^X }[/math] is union-closed with [math]\displaystyle{ \emptyset\in\mathcal{A} }[/math].
Canonical systems
There are at least three canonical systems of Horn clauses that describe a given union-closed family.
Maximal one
Considering all [math]\displaystyle{ (x,S) }[/math] that are satisfied by [math]\displaystyle{ \mathcal{A} }[/math] characterizes [math]\displaystyle{ \mathcal{A} }[/math]. To see this, we need to show that every set not in [math]\displaystyle{ \mathcal{A} }[/math] violates some [math]\displaystyle{ (x,S) }[/math]. Indeed for [math]\displaystyle{ A\not\in\mathcal{A} }[/math], take some [math]\displaystyle{ x\in A }[/math] that is not an element of any [math]\displaystyle{ \mathcal{A} }[/math]-member contained in [math]\displaystyle{ A }[/math]; this is possible due to the union-closure assumption. Then put [math]\displaystyle{ S:=X\setminus A }[/math].
In most cases, there are smaller systems of Horn clauses that still characterize [math]\displaystyle{ \mathcal{A} }[/math]. The following is taken from this paper, which investigates the dual notions for intersection-closed families.
Using minimal transversals
It is sufficient to consider those [math]\displaystyle{ (x,S) }[/math] for which [math]\displaystyle{ S }[/math] is not contained in any other [math]\displaystyle{ S' }[/math] for which [math]\displaystyle{ (x,S') }[/math]. In other words, [math]\displaystyle{ S }[/math] can be assumed to be a minimal transversal of [math]\displaystyle{ \mathcal{A}_x }[/math].
Various reformulations of this can be found in the paper above.
Using free sets
A set [math]\displaystyle{ S }[/math] is free if for every [math]\displaystyle{ y\in S }[/math] there is [math]\displaystyle{ A\in\mathcal{A}_y }[/math] with [math]\displaystyle{ A\cap S = \{y\} }[/math]. (At least this is the terminology used in the dual case of intersection-closed families, where it seems to be motivated by the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses [math]\displaystyle{ (x,S) }[/math] with [math]\displaystyle{ S }[/math] free and [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ A\cap S=\emptyset }[/math] implies [math]\displaystyle{ x\not\in A }[/math].
Literature
For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is a survey.
