In a collection {$S_1, S_2, ... S_n$} of $n\geq 2$ nonempty sets, no two sets have the same number of elements. Show that this collection has a system of distinct representatives

(a) by using Hall's theorem: A collection {$S_1, S_2, ... S_n$} of $n$ nonempty finite sets has a system of distinct representatives if and only if, for each integer $k$ with $1\leq k\leq n$, the union of any $k$ of these sets contains at least $k$ elements.

(b) without using Hall's theorem.

It seems that I should begin by letting $|S_1|<|S_2|<\cdots<|S_n|$ and showing that, for any union of these sets, I will always get at least $k$ elements. It seems clear to me that the result is true, but I don't know how to prove this exactly.

  • 2
    $\begingroup$ Try using the pigeonhole principle. $\endgroup$ – Gregory J. Puleo Nov 12 '15 at 2:26

HINT: For (a), show that $|S_k|\ge k$ for $k=1,\ldots,n$, and note that if $F\subseteq\{1,\ldots,n\}$, then

$$\left|\bigcup_{k\in F}S_k\right|\ge|S_{\max F}|\;.$$

For (b), suppose not, and let $F\subseteq\{1,\ldots,n\}$ be minimal such that $\{S_k:k\in F\}$ has no SDR. Let $m=\max F$. Let $T$ be an SDR for $\{S_k:k\in F\setminus\{m\}\}$. How must $S_m$ be related to $T$? Is this actually possible?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.