I have chosen combinatorics as my elective in my $3^{\text{rd}}$ semester.There is a theorem in combinatorics known as Hall's marriage problem.Let us first define some terminologies:
Defn. A system of distinct representatives for a sequence of sets $S_1,S_2,…,S_m$(not necessarily distinct) is a sequence of distinct elements $x_1,…,x_m$ such that $x_i\in S_i$ for all $1\leq i\leq m$.
Now the statement of Hall's theorem is as follows:
Th. The sets $S_1,S_2,…,S_m$ have a sequence of distinct representatives if and only if for every $I\subset \{1,2,…,m\}$,$|\bigcup\limits_{i\in I} S_i|\geq |I|$.
But I find this theorem hard to remeber because I don't understand what it really means.I have searched on internet but there it is something a bit different and explained using graph theory which I have not studied yet.So,I am looking for intuition behind this theorem.Can someone explain with a suitable example?
Best Answer
Let me try and give an intuitive example. In your school there are $m$ different clubs: a sports club, chess club, math club, music club, etc. These correspond to the $m$ sets $S_1, \cdots, S_m$. The clubs are not independent because some people are in multiple clubs. The principal wants to meet with members of each club, so a representative must be chosen for each club. In addition, the principal insists that a single person cannot represent two clubs -- if you belong to both the math and music club, you can represent at most one. The question is -- is this possible?
Suppose that me and two friends got bored and decided to make four clubs just for us, based on our various niche interests. This will cause a problem, as we are three people and we cannot represent four clubs. Let's denote our four clubs $S_1, S_2, S_3, S_4$. This problem of having only three people represent four clubs can be written as $|\bigcup_{i=1}^{4}S_i| = 3 < 4$. In general, for any collection of clubs $I \subset \{1, \cdots, m\}$, if we find out that these clubs have fewer than $|I|$ people in total, we will end up with too few representatives, and again we will be stuck. Mathematically, this is $|\bigcup_{I}S_i| < |I|$. This proves half of the theorem: if $|\bigcup_{I}S_i| < |I|$, then certainly we cannot find enough representatives.
The theorem says that this is the only obstruction to finding enough representatives. As long as you can be sure that $|\bigcup_{I}S_i| < |I|$ never happens, you can find distinct representatives for each club. This is a common kind of result in math -- you identify an "obvious" obstruction to something happening, and then you prove that this is the only possible obstruction, giving a sufficient and necessary condition.