Posted by: yanzhang | January 20, 2009

## Connections: Hall’s Marriage Theorem, Konig’s Theorem, Max-cut / Min-flow

In my increasing old age, I’ve glumly realized that my memory capacities lie somewhere 3 standard deviations down in the murky bottom of the gene pool. This spells disaster for my life ahead as a mathematician, but I struggle to compensate by remembering as few things as possible by cutting out expendable chunks such as needing to eat, birthdays (others and my own), and multiple instances of the same mathematical theorem. This is why I was really happy and angry when I realized that three theorems I have come to love are really the same thing. Happy because it means there are two fewer things to remember, angry because I really should have known this sooner (and I’m sure many of you have already taken this for granted). Cest la vie.

I. Hall’s Marriage Theorem: given a bipartite graph with parts $A$ and $B$, there exists a matching of $A$ into $B$ if and only if for any subset $I \subset A$, the corresponding subset of vertices in $B$ with at least one edge connected to some vertex in $I$ has cardinality at least that of $I$.

II. A ubiquitous nameless lemma about $0-1$ matrices that I have seen in at least 3 places: given such a matrix, the minimal number of rows and/or columns to cover all the $0'$s is the same as the maximum number of $0'$s we can find such that no two are in the same row or column.

III. Konig’s Theorem: in a bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Since they don’t always come up in the same context, I’ve always treated them as different chunks of information to package into my brain. Now that they’ve been juxtoposed I guess it should have been more obvious, but it took this old geezer a while to realize that yes, they are all the same (thanks to the principle of max-cut and min-flow).

For (I), this is classical. The main upshot is that the maximal matching is the same as a maximum flow, when you add a source that goes to all the vertices of $A$ and a sink that comes from all the vertices of $B$. This is a favorite space-filler of college courses, so I’ll omit the rest.

For (III), I randomly realized you can do the same here: add a source and a sink as before. Then the matching is the flow and a cover is just a cut (since we need all of the edges to be cut).

For (II), the subtlety is only a slight deterrant. This was the main cute idea that I realized while cooking breakfast, inexplicably and unfortunately unduplicably inspired by oatmeal and camomile tea: make a bipartite graph with parts $A$ and $B$ out of the matrix, where the rows correspond to the vertices in A and the columns correspond to the vertices in B, let there be an edge when the corresponding matrix entry has a 0 and no edge otherwise. Then a matching is just a set of $0'$s with no two in the same row or column, and a vertex cover is just a set of rows and columns (a row corresponds to a vertex cover of the corresponding vertex in A, and similarly for columns and B). There.

-YZ

P.S. Of course I was speaking in jest about needing to forget – even if statements are equally strong, there are definitely situations that call for one instead of another. Look at the Axiom of Choice – or my less-cliched favorite example of equivalent things that are obviously non-equivalent: the “weak” Nullstellensatz and the “real” Nullstellensatz. I’m just old and grumbling.

P.P.S. Yes, I know there is also Dilworth’s theorem. However, I feel the more “immediate” links between these is max-flow / min-cut.

P.P.P.S. I’m not actually that old.

## Responses

1. Just to let you know, your LaTeX symbols display correctly when someone browses to your blog, but they show up as “No formula provided” in Google Reader.

2. It sounds like you would find this recent discussion in Gowers’ blog very relevant:

http://gowers.wordpress.com/2008/12/28/how-can-one-equivalent-statement-be-stronger-than-another/

I also talked about the weak and strong nullstellensatz (or nullstellensätze?) at

http://terrytao.wordpress.com/2007/11/26/hilberts-nullstellensatz/

and on the max cut/min flow theorem and related results (Menger, Hall, etc.) at

http://terrytao.wordpress.com/2007/11/30/the-hahn-banach-theorem-mengers-theorem-and-hellys-theorem/

3. There a book you might enjoy, by Reichmeider, which goes into the equivalence of the combinatorial theorems you’ve mentioned, and some others.

4. Just to let you know, II (nameless lemma) is a special case of the Konig’s theorem.