Studying the proof of Hall's theorem in my book I started to wonder if there is a shorter way to prove it. Following is an attempt that I think works but (being short) makes me wonder if I made a mistake. Can someone double check?

For a collection of sets $S_1,\ldots,S_m$ we say that they have a collection of distinct represenatives if there exists distinct elements $x_1,\ldots,x_m$ such that $x_i \in S_i$ for $i = 1,\ldots, m.$ We say that our collection of sets satisfies Hall's criterion if $$ \left |\bigcup_{i \in I} S_i \right | \geq |I| \quad \mbox{for all } I \subseteq \{1,\ldots,m\}.$$

Claim. If $S_1,\ldots,S_m$ satisfy Hall's criterion then they have a set of distinct representatives.

Proof. We prove the claim by induction on $m.$ For $m=1$ the claim is obvious so suppose the claim holds for all $m < k$ for some $k$ and let $S_1,\ldots,S_m$ be a collection of sets satisfying Hall's criterion. Let $\{x_1,\ldots,x_{m-1}\}$ be the set of distinct representatives for $S_1,\ldots,S_{m-1}$ guaranteed by the indcution hypothesis. If $\{x_1,\ldots,x_{m-1}\} \ne S_m$ then we are done. If $\{x_1,\ldots,x_{m-1}\} = S_m$ that then $ \left |\bigcup_{i=1}^{m-1} S_i \right | > m-1$ since otherwise $S_1,\ldots,S_m$ do not satisfy Hall's criterion. But this implies that for some $i$ there exist a $x_i' \in S_i$ such that $x_i' \not \in S_m$ and hence we can take $\{x_1,\ldots,x_{i-1}, x_i',x_{i+1},\ldots,x_{m-1},x_i\}$ as our set of distinct representatives. $\square$

Anyone happens to see a flaw in the above proof?


When you say "If $\{x_1, \ldots, x_{m-1}\} \ne S_m$ we are done", I do not see why that is the case. It could be that $S_m$ is a proper subset of $\{x_1, \ldots, x_{m-1}\}$, in which case your subsequent argument does not work, because you do not know that $x_i \in S_m$.

  • $\begingroup$ You're right thanks! I am wondering if the above argument could be corrected to fix this bug in the proof. $\endgroup$ – Jernej Apr 22 '13 at 16:09
  • $\begingroup$ I don't see an easy correction. The problem is, suppose you had $S_1 = S_2 = \ldots = S_{m-1} = S$ where $S$ is some set of size $m$, but $S_m$ consists of just a single element from $S$. Then Hall's criterion is clearly satisfied, but you have to choose the representatives from $S_1, \ldots, S_{m-1}$ carefully, avoiding the element in $S_m$. However, when you start the argument with "by induction there are representatives from $S_1, \ldots, S_{m-1}$" you have no control over the representatives you get. $\endgroup$ – Ted Apr 22 '13 at 16:17
  • $\begingroup$ Wouldn't it work to say given that $S \subseteq \{x_1,\ldots,x_m\}$ take all the sets that intersect with $S$ and apply a similar argument to these sets? $\endgroup$ – Jernej Apr 22 '13 at 16:21
  • $\begingroup$ I don't understand; can you elaborate further? One thing I thought of, but does not work, is this: Suppose that $S_m = \{x_1, \ldots, x_k\}$ for some $k<m$, and suppose $x_i \in S_i$ for $1 \le i \le k$. Then by Hall's criterion $\{S_1, S_2, \ldots, S_k, S_m\}$ has at least $k+1$ elements together, so there is some element $x$ in one of these $S$'s that is not in $S_m$. The problem is that $x$ could already be used as the representative from another $S_i$ where $i>k$. $\endgroup$ – Ted Apr 22 '13 at 16:35
  • $\begingroup$ Yes! This was precisely what I meant! I see the problem now as well. Thank you for your clarifications! $\endgroup$ – Jernej Apr 23 '13 at 6:02

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.