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.

  • $\begingroup$ Do you mean in your last sentence "it restricts the form of $S$"? $\endgroup$ – Wolfgang Apr 11 '13 at 10:27
  • 1
    $\begingroup$ 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) $\endgroup$ – Wolfgang Apr 11 '13 at 10:46
  • $\begingroup$ Thanks Wolfgang, yes I did mean that and have edited. $\endgroup$ – Allen Knutson Apr 11 '13 at 11:16
  • $\begingroup$ 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). $\endgroup$ – Vidit Nanda Apr 11 '13 at 14:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.