3
$\begingroup$

Let $V$ be a set and $E$ a set of subsets of $V$. I'd like to know the proper terminology for the following concept.

Let me call it "generator". A generator is a set $F$ of subsets of $V$ such that every $e \in E$ is the union of elements of $F$. (No intersections allowed.)

(One is then interested in finding properties of "generators" of $(V,E)$, e.g., for finite $V$, the minimum cardinality of a "generator" $F$.)

Improve this question
$\endgroup$
2
  • $\begingroup$ This isn't an answer but I think we can translate the question to algebras as follows. Let V={x_1,x_2...} then let and edge be labeled by the vertices it contains. Then you are looking for squarefree monomial algebras that contain the algebra k[e_1,...] in their radical. Maybe this would give a new way to view the problem. $\endgroup$
    – Stephen Sturgeon
    Jul 31, 2013 at 16:11
  • 1
    $\begingroup$ The terminology varies. One use I like is that F is a base. One has to take care that it is a base with (respect to) operation union. You can search the literature on union-closed sets for more examples of terminology. Papers that cite Poonen (1990 or1992; I'm not sure of the date) are a good start. $\endgroup$
    – The Masked Avenger
    Jul 31, 2013 at 16:28

1 Answer 1

Reset to default
1
$\begingroup$

This problem is equivalent to the following. In the strong group testing model (http://en.wikipedia.org/wiki/Group_testing) are goal is to identify some defective elements, that can be any set of a given closed system $D$, or maybe they are not, in which case we only have to output that they are not. In the non-adaptive model, we have to give our questions in advance, each of which is a set, and the answer is yes if and only if it contains a defective element. It was noticed by Peter Damaschke and it is not hard to prove that a set of questions solves the problem if and only if the complement of any element of $D$ can be covered by a union of them. So if $D=\{ V\setminus e \mid e\in E\}$, then we get exactly your problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.