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:
“Nature’s law says that the strong must prevent the weak from living, but only in a newspaper article or textbook can this be packaged into a comprehensible thought. In the soup of everyday life, in the mixture of minutia from which human relations are woven, it is not a law. It is a logical incongruity when both strong and weak fall victim to their mutual relations, unconsciously subservient to some unknown guiding power that stands outside of life, irrelevant to man.”
—Anton Pavlovich Chekhov (1860–1904)