I fully understand Hall's marriage theorem, if I have $n$ boys and $m$ girls and if every subset of $k$ boys knows at least $k$ girls then there exists a matching between the boys and girls. What happens if we now consider a village with infinitely many boys and girls? If the marriage condition still holds does Hall's marriage theorem still hold and that there is a matching?
$\endgroup$1 Answer
$\begingroup$Unfortunately, it does not hold. Let $B=\{b_0,b_1,b_2\ldots\}$ be the set of boys, and $G=\{g_1,g_2,\ldots\}$ be the set of girls, i.e., each number of boys and girls is countably infinite. Assume below conditions:
- Boy $b_0$ knows every girl, and
- boy $b_i$ knows girl $g_i$ for all $i \geq 1$.
Then it satisfies Hall's marriage condition. However, there is no matching cover $B$.
I referred:
I don't know the infinite Hall's marriage theorem holds if the condition has more restriction: Each boy know only finitely many girls.
$\endgroup$ 3
