Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In Hall's Marriage Theorem, we have a set $B$ of brides and $G$ of grooms, where each bride $b$ has an acceptable set $A_b \subseteq G$ of grooms. A matching $m:B\to G$ is an injection such that $m(b) \in A_b$ for each $b\in B$. (So each bride gets married, but some grooms may be out of luck.) Obviously, if there's some set $S \subseteq B$ of brides such that $|\cup_{b\in S} A_b| < |S|$, then a matching is impossible; the theorem is that this is the only obstruction.

I'm interested in the case that $G$ is an interval $[1,n]$ in $\mathbb N$, and each $A_b$ is a subinterval $[i,j]$. (Perhaps each bride is only willing to accept grooms within a certain range of heights.) I have been able to make the following refinement: if no matching is possible, then there is an interval $[x,y]$ such that $|[x,y] \cap G| < |\{b : A_b \subseteq [x,y]\}|$.

(This is an improvement in two ways -- it restricts the form of $S$, plus the left side is a priori larger than $|\cup_{b\in S} A_b|$.)

Is this refinement known?

This extension wasn't very difficult, but if it was known I'd rather give credit to its earlier discoverers.

share|improve this question
Do you mean in your last sentence "it restricts the form of $S$"? –  Wolfgang Apr 11 '13 at 10:27
Also, I guess you could further generalize it by replacing "intervals in $\mathbb N$" with "sets in $\mathbb N^m$ that are convex hulls" or "convex sets in $\mathbb N^m$". (not sure if the latter works, as intersections may not be convex) –  Wolfgang Apr 11 '13 at 10:46
Thanks Wolfgang, yes I did mean that and have edited. –  Allen Knutson Apr 11 '13 at 11:16
I haven't seen this generalization before, but you should make sure it doesn't follow obviously from something like exercise III.4.6 in Bourbaki's set theory (I don't think it does, but it's too early in the morning). –  Vidit Nanda Apr 11 '13 at 14:03
add comment

Your Answer


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

Browse other questions tagged or ask your own question.