# Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?

I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I was interested to see that it is regarded as equivalent to several other fundamental theorems in combinatorics, for instance Dilworth's Theorem on posets of finite width and König's Theorem on matching in (finite?) graphs. I was able to track down the proofs of these equivalences online.

However, the article also claims that Hall's Marriage Theorem is equivalent to the (König-)Birkhoff - von Neumann Theorem, which asserts that a real matrix is doubly stochastic iff it is a convex combination of permutation matrices (if you know the Minkowski-Krein-Milman theory of extreme points in convex sets, then an equivalent assertion is that the doubly stochastic matrices form a compact convex subset of $M_n(\mathbb{R})$ with extreme points precisely the permutation matrices, and since there are finitely many extreme points one has in fact a convex polytope, the Birkhoff polytope).

But the attribution here is strange: the only citation is to this series of slides by R.D. Borgersen, for which the title is "Equivalence of seven major theorems in combinatorics"...but it only shows some of the implications! In particular, it is not shown that Birkhoff - von Neumann implies any of the theorems as above. So now we get to the question in my title: does it?

As a secondary question, is there a nice source which treats all these theorems (maybe not Birkhoff - von Neumann, but the other five or six, depending on how you count) at once? In particular much of the literature I've found seems to be a bit sloppy on whether the structures involved need to be finite: it seems that "some, but not all" finiteness conditions are needed for these theorems to hold and that the folkloric equivalence is understood to apply in the finite case only. Is this correct?

• As an MO-veteran, you're certainly aware of this thread but I'm not sure if anything there relates to your question directly. I just thought it might be worth pointing it out for other readers. – t.b. Jun 23 '11 at 15:55
• Wikipedia is mistaken, I think. The section on logical equivalences was added by Robert Borgersen himself, so you can ask him about it. :-) That section has been questioned multiple times (also search the talk page for "equival"), so it shouldn't be taken seriously, probably. – ShreevatsaR Jun 23 '11 at 17:38
• @ShreevatsaR: I did see the doubts expressed on the wikipedia page, thanks. Still, I am taking it seriously enough to ask the question... – Pete L. Clark Jun 23 '11 at 18:04
• Sorry, didn't mean to offend you (if I did); was just pointing out something I remembered about the history of the Wikipedia page. I know the question still stands; I have wondered about this myself, so thanks for asking it. – ShreevatsaR Jun 23 '11 at 18:24
• @Shree: absolutely no offense taken. Thanks for your comment. – Pete L. Clark Jun 23 '11 at 18:33

The book you want is Reichmeider, The Equivalence of Some Combinatorial Matching Theorems. Alas, it is long out of print.

[Added by PLC: I am taking the liberty of reproducing the MathSciNet review. Note that it does not mention Birkhoff - von Neumann, though this is hardly conclusive.]

It is well known that various theorems concerning bipartite matchings and network flows are all "equivalent'', in the sense that any one may be deduced easily from any other. This expository work painstakingly organises and presents various proofs of these results and of the relationships. It focusses on theorems of König and Egerváry, Hall, Dilworth, Menger, Ford and Fulkerson, and Hoffman. The book deals only with the finite case, and does not consider matroids or algorithms. (Reviewed by Colin J.H. McDiarmid)

It certainly implies the Koenig marriage theorem. Given a regular bipartite graph on vertex set $U \sqcup V$, define a "modified" adjacency matrix $A = (a_{ij})$ by $a_{ij} = 1$ if element $i$ of $U$ is adjacent to element $j$ of $V$, and $a_{ij} = 0$ otherwise. Since each row and column of $A$ adds to the degree, you can normalize it to get a doubly stochastic matrix whose nonzero entries still record adjacency in the graph. Write this as a convex combination of permutation matrices, pick one of them, and use it as a modified adjacency matrix of a matching (since its nonzero entries must be nonzero in $A$, this is contained in the original graph).

To get the full Hall theorem, you need to check that the Hall condition is enough to do the doubly stochastic normalization, which I don't see but sounds reasonable.

EDIT: I misunderstood which Koenig theorem you meant. Sorry!

• What is the "Koenig marriage theorem"? (If you're wondering, I am not an expert in this stuff...) – Pete L. Clark Jun 23 '11 at 16:34
• Maybe it's the statement that every regular bipartite graph has a perfect matching? If so, as you say it is a priori weaker than Hall's theorem... – Pete L. Clark Jun 23 '11 at 16:44
• Yes, that's what I meant, and it's definitely weaker than Hall's theorem (inasmuch as one truth is weaker than another). Sorry for the misunderstanding! – Tournabout Jun 23 '11 at 17:26