3
$\begingroup$

Hall's marriage theorem states that a collection of men can get married iff for every group of $k \geq 1$ men, the total number of women that like one or more of them is at least $k$. For example, if:

  • $M_1$ is liked by $W_1$ and $W_2$;
  • $M_2$ is liked by $W_2$ and $W_3$;
  • $M_3$ is liked by $W_3$ only.

Then the condition is satisfied and so a matching exists ($W_1$-$M_1$, $W_2$-$M_2$ and $W_3$-$M_3$).

But what happens if the men come serially? For example, let's suppose that $M_1$ comes first and selects any woman that likes him; then $M_2$ comes and selects any remaining woman that likes him; etc. In this case, the process will not necessarily conclude with a successful matching! For example, it is possible that:

  • $M_1$ selects $W_2$;
  • $M_2$ selects $W_3$;
  • $M_3$ now remains lonely because the only woman that liked him is already married!

However, if $M_3$ is liked by all women, then the selection always concludes with a marriage, regardless of what $M_1$ and $M_2$ do.

MY QUESTION IS: What conditions, stronger than Hall's marriage condition, guarantee that, for every selection of each man $M_i$, the following men in the series ($M_j$ for $j>i$) can select women that like them, so that the selection always concludes with all men being married?

NOTES:

  • The number of women can be equal or larger than the number of men.
  • The order of men is pre-specified ($M_1$, ..., $M_n$); only the selection of each man is unknown in advance.
$\endgroup$
0
$\begingroup$

If you're looking for a sufficient condition (Your question is "what conditions guarantee"), here's a simple one : if every women likes only one man, and no pair of women like the same man, then there is a match.

But I assume you are looking for a necessary and sufficient condition ?

$\endgroup$
  • $\begingroup$ Yes, I am looking for a necessary and sufficient condition (or at least, a stronger sufficient condition) $\endgroup$ – Erel Segal-Halevi Nov 5 '14 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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