27
$\begingroup$

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:

  • Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into 1st and 2nd class citizens. Suppose that Hall's condition is satisfied for 1st class citizens. That is, for every set $M\subset\{\text{1st class boys}\}$ there are at least $|M|$ girls (from both classes) adjacent to $M$. And similarly for every $W\subset\{\text{1st class girls}\}$ there are at least $|W|$ boys adjacent to $W$. Then there exists a matching covering all 1st class citizens.

I need this fact as a lemma in a paper on geometric analysis. The proof is more or less straightforward but it occupies some space when written down. And I suspect that the fact may be well-known to specialists. Is this indeed the case and what are relevant references?

$\endgroup$
  • $\begingroup$ It's a really nice theorem and you should write down your proof. Should it go into your paper on geometric analysis? I don't know, but I wouldn't see a reason why not. $\endgroup$ – darij grinberg Apr 23 '15 at 19:29
  • 1
    $\begingroup$ @darij: Yes, of course we will prove it in the paper if there is no reference. It just looks too natural to be unknown. $\endgroup$ – Sergei Ivanov Apr 23 '15 at 20:14
  • $\begingroup$ Notice that your lemma generalizes Hall's theorem (just declare all boys to be 1st class and all girls to be 2nd class). $\endgroup$ – darij grinberg Apr 24 '15 at 0:38
  • $\begingroup$ Great question (and answer!). Have you already uploaded your article? I would be interested in seeing it! $\endgroup$ – Dominic van der Zypen Jun 23 '15 at 9:53
  • 3
    $\begingroup$ @Dominic van der Zypen: Yes we have just finished it. It is on arxiv.org/abs/1506.06781 $\endgroup$ – Sergei Ivanov Jun 24 '15 at 13:54
20
$\begingroup$

In this answer I sketch an easy proof of your lemma and then give some references.

The easy proof uses Knaster's fixed point theorem:

THEOREM. Let $S$ be any set (finite or infinite) and let $\varphi:\mathcal P(S)\to\mathcal P(S)$ be an order-preserving map, i.e., $X\subseteq Y\implies\varphi(X)\subseteq\varphi(Y).$ Then $\varphi$ has a fixed point.

PROOF. Let $X_0=\bigcup\{X\in\mathcal P(S):X\subseteq\varphi(X)\}.$ It is easy to see that $\varphi(X_0)=X_0.$

(Knaster's fixed point theorem was set as a Putnam Problem in 1957. The generalization to complete lattices is called the Knaster-Tarski Theorem.)

Now let $B_1,B_2,G_1,G_2$ be the set of all first-class boys, second-class boys, first-class girls, and second-class girls, respectively; $B=B_1\cup B_2,\ G=G_1\cup G_2,\ B_1\cap B_2=G_1\cap G_2=\emptyset.$ By Hall's theorem there are matchings $f:B_1\to G$ and $g:G_1\to B.$ Define an order-preserving map $\varphi:\mathcal P(B_1)\to\mathcal P(B_1)$ by setting, for $X\subseteq B_1,$ $$\varphi(X)=B_1\setminus g[G_1\setminus f[X]].$$ By Knaster's fixed point theorem we have $\varphi(X_0)=X_0$ for some $X_0\subseteq B_1$. Now we can match the boys in $X_0$ with the girls in $f[X_0]$ and the girls in $G_1\setminus f[X_0]$ with the boys in $g[G_1\setminus f[X_0]].$

Here are some references related to your lemma:

L. Mirsky, Transversal Theory, Academic Press, New York and London, 1971.

L. Mirsky and Hazel Perfect, Systems of representatives, J. Math. Analysis Appl. 15 (1966), 520-568.

O. Ore, Theory of Graphs, Amer. Math. Soc. Colloquium Publications No. 38, Providence, 1962 [Theorem 7.4.1].

Here is how your lemma is stated on p. 36 of Mirsky's book:

THEOREM 2.3.1. Let $(X,\Delta,Y)$ be a deltoid and let $X',Y'$ be admissible subsets of $X,Y$ respectively. Then there exist linked sets $X_0,Y_0$ such that $X'\subseteq X_0\subseteq X,\ Y'\subseteq Y_0\subseteq Y.$

The jargon is defined on pp. 33-34. Namely, a deltoid $(X,\Delta,Y)$ is a bipartite graph with partite sets $X,Y$ and edge set $\Delta$; a set $X'\subseteq X$ is admissible if there is an injective matching of $X'$ to $Y$; a set $Y'\subseteq Y$ is admissible if there is an injective matching of $Y'$ to $X$; two sets $X_0\subseteq X,Y_0\subseteq Y$ are linked if there is a bijective matching of $X_0$ to $Y_0.$

P.S. Sergei Ivanov has commented that the result, as stated in the question, can be traced back to Dulmage & Mendelsohn, Coverings of bipartite graphs, Canad. J. Math. 10 (1958) 517-534, Theorem 1.

$\endgroup$
  • 3
    $\begingroup$ Very nice proof! I like how it weaponizes one of the most trivial facts in mathematics. $\endgroup$ – darij grinberg Apr 24 '15 at 0:36
  • 4
    $\begingroup$ Thanks! I tracked it from Mirski & Perfect's paper down to Dulmage & Mendelsohn, Coverings of bipartite graphs, Canad. J. Math. 10 (1958) 517-534, Theorem 1. And there (unlike the other sources) it is exactly it, not something that one has to combine with Hall's Theorem. $\endgroup$ – Sergei Ivanov Apr 24 '15 at 1:12
  • $\begingroup$ @SergeiIvanov Hope you don't mind that I've incorporated your comment into my answer. Please feel free to remove or edit the postscript as you see fit. $\endgroup$ – bof Apr 24 '15 at 1:37
  • $\begingroup$ @bof: I think we are going to thank you in acknowledgements. Do you prefer to be mentioned as an anonym or by some real name? $\endgroup$ – Sergei Ivanov Apr 29 '15 at 13:12
  • $\begingroup$ It hardly seems necessary, but if you are going to thank me in the paper for putting you on the trail of that reference, you may as well use my real name (which I am now emailing to you) instead of the silly and slightly impolite acronym I use here. $\endgroup$ – bof Apr 29 '15 at 23:08
10
$\begingroup$

I have not seen it stated anywhere, but I would call it a corollary of Hall. It is in fact very natural, so it would not surprise me if it has been stated before.

Simplest proof I can come up with using Hall:

Hall gives you a matching from the first class boys into the girls, and a matching from the first class girls into the boys, record all these edges with this direction to get a directed graph, which consists of directed paths and even cycles. Delete every other edge in every cycle, and delete the second, fourth, etc. edge of every path. Note that the last vertex in every path is 2nd class, so this yields a matching covering all first class vertices.

$\endgroup$
  • 1
    $\begingroup$ Yes, we have the very same argument. It would be 5 lines long if we were aiming at combinatorialists. But it took more than a page to make the text consumable by analysts. $\endgroup$ – Sergei Ivanov Apr 23 '15 at 21:43
  • $\begingroup$ Why do you assume that analysts can't understand the five-line version? $\endgroup$ – David Richerby Apr 24 '15 at 14:40
  • 7
    $\begingroup$ @David: Because we tested it on live analysts. It turns out that the very language of graph theory is not as widely understood as one might hope. $\endgroup$ – Sergei Ivanov Apr 29 '15 at 13:19

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.