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:
“The contention that a standing army and navy is the best security of peace is about as logical as the claim that the most peaceful citizen is he who goes about heavily armed. The experience of every-day life fully proves that the armed individual is invariably anxious to try his strength. The same is historically true of governments. Really peaceful countries do not waste life and energy in war preparations, with the result that peace is maintained.”
—Emma Goldman (1869–1940)