# Computing the union-closure of a finite discrete set

You must excuse my notation if it is not stndard, I have my background in Computer Science and not in Math. Hope this topic still is in the right forum.

Let $U = {1,2,...,n}$ be our finite universe. Let $\mathcal{F}$ be a family of subsets of $U$.

The union-closure of $\mathcal{F}$ is the unique minimal family $\mathcal{C}_{\mathcal{F}}$ such that:

1. Every element in $\mathcal{F}$ is in $\mathcal{C}$.
2. For every pair of elements in $\mathcal{C}$ their union is also in $\mathcal{C}$.

I have a couple of questions regarding the union-closure.

1. How fast can we compute the union-closure?
It can be done in $O(|\mathcal{C}| \cdot \log{|\mathcal{C}|} \cdot n^2)$.

2. Can we bound $\log_2{|\mathcal{C}|}/n$ as $n$ goes to infinite?
The set system can be modelled as a bipartite graph (sets on one side and U on the other edges)
Then we can make a lower and upper bound based on the Maximum Matching and Maximum Induced Matching (equivalent to VC-dimension).
Does anyone know of work related to this?

-
Even if it has sets, it's not really set theory. I removed the tag. – Asaf Karagila Dec 15 '11 at 23:33
Without conditions on $\mathcal{F}$, $\log_2|\mathcal{C}|/n$ can range from $0$ if, say, $\mathcal{F}=\{U\}$, to $1-\epsilon$, if $\mathcal{F}=\{\{k\}:k\in U\}$, where $\epsilon\to 0$ as $n\to\infty$. – Brian M. Scott Dec 15 '11 at 23:47
Interesting question: you might consider asking it (if you don't get answers here) on cstheory.stackexchange.com – Suresh Venkat Dec 21 '11 at 0:31