# Questions tagged [set-system]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
2 votes
1 answer
175 views

### Is counting the union of power sets NP-complete?

Say we have $n$ sets $A_1,\dots,A_n$ with elements from a universal set $U$. We want to compute the cardinality of $\cup_{i=1}^n 2^{A_i}$ or at least decide on non-trivial bounds. Is this problem NP-...
11 votes
3 answers
819 views

### Applications of sunflower lemma in theoretical computer science

In one lecture by Kewen Wu who is one of the authors of paper Improved bounds for the sunflower lemma, it is said that the sunflower lemma can be applied to many fields like circuit lower bounds ...
• 490
6 votes
0 answers
354 views

### Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
• 679
4 votes
1 answer
100 views

### Do these set systems imply a partition?

During research, I hit a set theoretic claim that I could neither proof nor disproof. Let $S_1,S_2,S_3$ be three set systems over the same finite universe $U$ such that $S_1,S_2,S_3$ are closed w.r....
• 439
1 vote
1 answer
751 views

• 2,153
2 votes
1 answer
200 views

• 2,482