20
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you mean in your last sentence "it restricts the form of $S$"? $\endgroup$
    – Wolfgang
    Commented Apr 11, 2013 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
    Commented Apr 11, 2013 at 10:46
  • $\begingroup$ Thanks Wolfgang, yes I did mean that and have edited. $\endgroup$
    – Allen Knutson
    Commented Apr 11, 2013 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
    Commented Apr 11, 2013 at 14:03
  • $\begingroup$ This is of course too late and probably does not differ from your argument, but for what it worth. We may reformulate the Hall condition in terms of grooms: the obstruction is provided by a set $T$ of grooms such that $|b:A_b\subset T|>|T|$. Then it is clear that if $T$ is an obstruction, then one of its "connected components" also is an obstruction. $\endgroup$
    – Fedor Petrov
    Commented Apr 18, 2019 at 9:15

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .