Union of each family is not the whole set

83 Views Asked by At

Let $n\geq k>0$, and consider all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. We want to partition it into families so that the union of each family is not equal to $A$. At least how many families do we need?

When $k=0$ or $k=n$, there is only one subset, so one family is enough.

When $k=1$, two families would be enough.

When $k=n-1$, any two subsets combine to $A$, so we need $n$ families.

For any $k$, it is true that $k+1$ families are always enough. We can have a family of all subsets without $1$, a family of all subsets without $2$, etc. (Choose arbitrarily if a subset falls into more than one category.) Since no subset can contain all of $1,2,\ldots,k+1$, every subset falls into some category. Is $k+1$ the best possible?

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose $S_1,\ldots,S_k$ is such a partition. For each $i$, since $\bigcup S_i \neq A$, there is some element $\alpha_i$ that all sets in $S_i$ miss. Consider now the subset $T = \{\alpha_1,\ldots,\alpha_k\}$, and an arbitrary $U \supseteq T$ of size $k$. None of the families $S_i$ contain $U$, hence $S_1,\ldots,S_k$ is not a partition.