Logical Equivalences
This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles. These include:
- The König–Egerváry theorem (1931) (Dénes Kőnig, Jenő Egerváry)
- König's theorem
- Menger's theorem (1927)
- The max-flow min-cut theorem (Ford–Fulkerson algorithm)
- The Birkhoff–Von Neumann theorem (1946)
- Dilworth's theorem.
In particular, there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.
Read more about this topic: Hall's Marriage Theorem
Famous quotes containing the word logical:
“Grammar is a tricky, inconsistent thing. Being the backbone of speech and writing, it should, we think, be eminently logical, make perfect sense, like the human skeleton. But, of course, the skeleton is arbitrary, too. Why twelve pairs of ribs rather than eleven or thirteen? Why thirty-two teeth? It has something to do with evolution and functionalism—but only sometimes, not always. So there are aspects of grammar that make good, logical sense, and others that do not.”
—John Simon (b. 1925)