# Can someone explain the assumption in the proof? (Variant of Hall's Theorem)

Hall's theorem

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.

-
i have uploaded the site about the proof – Mathematics Feb 1 '12 at 3:17
Link doesn't work for me. Seems to be from Victor Bryant, Aspects of Combinatorics, but Google Books won't let me see the page or even the page number, and I don't have the book. – Gerry Myerson Feb 1 '12 at 3:17
@Gerry: I put in a picture of the relevant page. – Zev Chonoles Feb 1 '12 at 3:19

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.

-

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.

-
I think he was referring to lines 1 and 2 of the <= paragraph. This should have the word "respectively" added I think, that would clear up OP's problem. – Clinton Boys Feb 1 '12 at 3:34
I am sure that you are right that the reference is to those lines. What we are trying to prove there is, in the words of the theorem, "if any collection of the girls $G_{i_1},\dots,G_{i_s}$ knows between them at least $b_{i_1}+\cdots+b_{i_s}$ boys, then the girls' demands can all be satisfied." We prove it by assuming the hypothesis, and deducing the conclusion. Lines 1 and 2 are the assuming-the-hypothesis part, and the hypothesis has the sum, not a "respectively" with commas. So I don't see how you can be right. – Gerry Myerson Feb 1 '12 at 5:11
You're absolutely right. I'll take down my answer for the second part. – Clinton Boys Feb 1 '12 at 6:31

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

-
Why it has to consider the subcollection ? – Mathematics Feb 1 '12 at 3:22
Because that's how Hall's Theorem works - it says you can match the elements of two sets in appropriate ways if and only if each of the subsets of one of the sets has some particular property. So, you have to look at subsets. – Gerry Myerson Feb 1 '12 at 3:25
Does it mean that i can say like $G_1,G_2,...G_r\in G_{i_1}$ and $G_{r+1},...,G_x\in G_{i_2}$ adn so on??? – Mathematics Feb 1 '12 at 8:29
No. $G_{i_1}$ is a girl, not a collection of girls. $\lbrace\,G_{i_1},\dots,G_{i_s}\,\rbrace$ is a collection of girls. – Gerry Myerson Feb 1 '12 at 11:53
so $G_{i_1}$ can be any one of the girl $G_1,...,G_n$ right?? – Mathematics Feb 2 '12 at 7:45