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:
- Every element in $\mathcal{F}$ is in $\mathcal{C}$.
- 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.
How fast can we compute the union-closure?
It can be done in $O(|\mathcal{C}| \cdot \log{|\mathcal{C}|} \cdot n^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?