Questions tagged [set-system]

The tag has no usage guidance.

2 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
AmeerJ's user avatar
  • 679
4 votes
0 answers
70 views

Set-systems with some version of independence

Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = m}}...
Ramprasad's user avatar
  • 2,482