Horn clause formulation

From Polymath1Wiki
Jump to: navigation, search

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

Canonical systems

There are at least three canonical systems of Horn clauses that describe a given union-closed family.

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 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]. 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](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 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

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.