Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 – Suresh Venkat Dec 21 '11 at 0:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.