Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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 cstheory.stackexchange.com –  Suresh Venkat Dec 21 '11 at 0:31

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.