2
$\begingroup$

Hall's theorem

enter image description here

Why it has to assume that the r girls consist of at least one 'copy' of each of the girls $G_{i_1} , ... , G_{i_s}$ in the prove of the converse.

Thanks.

  • 0
    @Gerry: I put in a picture of the relevant page.2012-02-01

3 Answers 3

0

If $G$ is a girl, let $b(G)$ be the number of boys that $G$ wants to marry. If $\mathscr{G}$ is any collection of the girls, let $b(\mathscr{G})=\sum_{G\in\mathscr{G}}b(G)\;,$ the total number of husbands desired by the girls in $\mathscr{G}$.

The converse of the theorem says that if every subset $\mathscr{G}$ of the girls knows at least $b(\mathscr{G})$ boys, then they can all find enough husbands from among the boys whom they know. The author proves this by reducing it the basic marriage theorem, in which each girl wants a single husband.

He does this by pretending that each girl $G$ is really $b(G)$ different girls, G_1',G_2',\dots,G_{b(\mathscr{G})}', who all know exactly the same boys as the real girl $G$, and each of whom wants just one husband. Thus, if we can arrange for each of these imaginary girls to get a husband from among the boys whom she knows, we can give the real girl $G$ these $b(G)$ husbands, and she’ll be happy.

In order to apply the basic marriage theorem, we need to know that its hypothesis is satisfied, i.e., that each collection of the imaginary girls knows at least as many boys as there are girls in the collection. So we imagine that we have a collection $\mathscr{C}$ of the imaginary girls; say that there are $s$ imaginary girls in $\mathscr{C}$. Each of these $s$ girls is an imaginary copy of one of the real girls. The real girls are $G_1,G_2,\dots,G_n$; for $k=1,\dots,n$ let $c(G_k)$ be the number of imaginary copies of girl $G_k$ in the collection $\mathscr{C}$. Note that $c(G_k)$ will be zero if $\mathscr{C}$ contains no imaginary copies of girl $G_k$. Now break up $\mathscr{C}$ into subcollections $\mathscr{C}_0,\dots,\mathscr{C}_n$: $\mathscr{C}_k$ is the set of imaginary girls in $\mathscr{C}$ who are copies of the real girl $G_k$. Thus, $\mathscr{C}_k$ contains $c(G_k)$ imaginary girls, all of whom know the $b(G_k)$ boys known to girl $G_k$. Now we’re in a position to say how many boys the imaginary girls in $\mathscr{C}$ know altogether.

Consider each subcollection $\mathscr{C}_k$ for $k=1,\dots,n$. If $c(G_k)=0$, $\mathscr{C}_k$ is empty, and we don’t have to worry about it: there aren’t any imaginary copies of girl $G_k$ in the collection $\mathscr{C}$. When the author said ‘assume that these $r$ consist of at least one “copy” of ...’, he was simply ignoring the real girls who have no copies in the collection that I’m calling $\mathscr{C}$.

If $c(G_k)>0$, $\mathscr{C}_k$ contains $c(G_k)$ imaginary girls who all know the same $b(G_k)$ boys. Thus, the total number of imaginary girls in $\mathscr{C}$ is

$s=\sum_{k=1}^nc(G_k)=\sum_{\substack{1\le k\le n\\c(G_k)>0}}c(G_k)\;,$

and the total number of boys known to these girls is

$\sum_{\substack{1\le k\le n\\c(G_k)>0}}b(G_k)\;.$

But recall that we made only $b(G_k)$ imaginary copies of girl $G_k$, so $c(G_k)\le b(G_k)$ for $k=1,\dots,n$, and therefore

$s=\sum_{\substack{1\le k\le n\\c(G_k)>0}}c(G_k)\le\sum_{\substack{1\le k\le n\\c(G_k)>0}}b(G_k)\;.$

In other words, the $s$ imaginary girls in the collection $\mathscr{C}$ know altogether at least $s$ boys, and the hypothesis of the basic marriage theorem is satisfied. It then says that we can successfully marry off all of the imaginary girls. If we now give each real girl $G$ all of the husbands allotted to her imaginary copies, she’ll get $b(G)$ husbands, one from each of her $b(G)$ copies, so she’ll be happy.

1

The $G_{i_j}$ are a subcollection of the collection $G_1,G_2,\ldots$ of all the girls.

  • 0
    so $G_{i_1}$ can be any one of the girl $G_1,...,G_n$ right??2012-02-02
1

For your second question, it means $b_{i_1}+\cdots+b_{i_s}$. That's the condition in the statement of the theorem, so that's the condition to assume in the proof.

  • 0
    You're absolutely right. I'll take down my answer for the second part.2012-02-01