Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Hall's marriage problem says $\{b_1,b_2,\dots,b_n\}$ and $\{g_1,g_2,\dots,g_n\}$ are $n$ boys and $n$ girls respectively. Let $G_i$=set of girls $b_i$ likes. Then a necessary and sufficient condition for a monogamous marriage to happen such that each $b_i$ gets married to a girl in $G_i$ (a compatible matching) is that for any $1\leq k\leq n$, and any $1\leq i_1< i_2<\dots< i_k\leq n$, cardinality of $G_{i_1} \cup \dots \cup G_{i_k}$ should be bigger than $k$ that is, take any $k$ boys then the total number of girls that these $k$ boys together like should be at least $k$.

There is apparently a version of marriage problem in which one considers both the sets- the set of girls whom each boy likes and set of the boys whom each girl likes. In that case the condition reduces to considering any k boys out of $\lceil n/2 \rceil$ instead of $n$ above.

Can someone tell me a good reference for this or a proof of this?

share|improve this question
6  
Awww... I thought you were actually having a problem with your marriage. –  The Chaz 2.0 Jul 14 '11 at 17:53
    
Is there any change that what you were interested in is the Gale-Shapley "marriage problem?" en.wikipedia.org/wiki/Stable_marriage_problem –  Joseph Malkevitch Jul 14 '11 at 23:07

1 Answer 1

I’ve not seen a version that exactly matches this description, but the following comes close. It considers only smaller sets, but it compensates by considering both sets of boys and sets of girls.

If $B$ and $G$ are the sets of boys and girls, respectively, for each $b \in B$ let $\overline G(b)$ be the set of girls whom $b$ does not like, and for each $g \in G$ let $\overline B(g)$ be the set of boys whom $g$ does not like. (It’s more convenient here to use these rather than $G(b)$ and $B(g)$, the sets of boys or girls liked by an individual, but the two are obviously interchangeable.) Then the boys and girls can be married off iff there do not exist $B_0 \subseteq B$ and $G_0 \subseteq G$ such that $|B_0| + |G_0| > n$, $G_0 \subseteq \bigcap_{b \in B_0} \overline G(b)$, and $B_0 \subseteq \bigcap_{g \in G_0} \overline B(g)$. Clearly if such $B_0$ and $G_0$ did exist, one of them would have to have cardinality at most $\lceil n/2 \rceil$.

Suppose that for each $B_1 \subseteq B$ and $G_1 \subseteq G$ of cardinality at most $\lceil n/2 \rceil$, $\left|\bigcap_{b \in B_1} \overline G(b) \right| < n - |B_1|$ and $\left|\bigcap_{g \in G_1} \overline B(b) \right| < n - |G_1|$. Suppose, to get a contradiction, that $B_0 \subseteq B$ and $G_0 \subseteq G$ are such that $|B_0| + |G_0| > n$, $G_0 \subseteq \bigcap_{b \in B_0} \overline G(b)$, and $B_0 \subseteq \bigcap_{g \in G_0} \overline B(g)$; without loss of generality $|B_0 \le \lceil n/2 \rceil$. But then $\left|\bigcap_{b \in B_0} \overline G(b) \right| < n - |B_0| < |G_0|$, so $G_0 \not\subseteq \bigcap_{b \in B_0} \overline G(b)$.

It only remains to check that the nonexistence of sets $B_0 \subseteq B$ and $G_0 \subseteq G$ such that $|B_0| + |G_0| > n$, $G_0 \subseteq \bigcap_{b \in B_0} \overline G(b)$, and $B_0 \subseteq \bigcap_{g \in G_0} \overline B(g)$ is equivalent to the usual formulation of the marriage condition, but this is pretty straightforward if one thinks in terms of the adjacency matrix of the obvious bipartite graph, as in this discussion.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.