# Marriage problem

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?

-
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

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.