دوشنبه‌ها در خرونینگن

The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.

If we let A_i be the set of men that the i-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a man if and only if the collection of sets {A_i} meets the marriage condition.

Note that the marriage condition is that, for any subset  of the women, the number of men whom at least one of the women would be happy to marry, , be at least as big as the number of women in that subset, . It is obvious that this condition is necessary, as if it does not hold, there are not enough men to share among the  women. What is interesting is that it is also a sufficientcondition.