3
$\begingroup$

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?

  • 6
    Awww... I thought you were actually having a problem with your marriage.2011-07-14
  • 0
    Is there any change that what you were interested in is the Gale-Shapley "marriage problem?" http://en.wikipedia.org/wiki/Stable_marriage_problem2011-07-14

1 Answers 1