1
$\begingroup$

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?

  • 0
    Interesting question: you might consider asking it (if you don't get answers here) on cstheory.stackexchange.com2011-12-21

0 Answers 0