6.10 ***Equivalent theorems to Hall’s matching theorem and more applications***

There are various powerful theorems in combinatorics and other areas that are equivalent to Hall’s marriage theorem. See https://en.wikipedia.org/wiki/Hall’s_marriage_theorem#Logical_equivalences

We have already seen Kőnig-Egervary theorem and Birkohoff-von Neumann theorem. We shall see three of them later, Max-flow min-cut theorem, Menger’s theorem (see Chapter 7) and Dilworth’s theorem (see Chapter 8).

Another non-trivial application of Hall’s marriage theorem is to show the existence of Haar measure on compact Topological groups. See [Krishnapur 2019, Part 4] for details on this result and also for more about the equivalences mentioned above.

Various other consequences of Hall’s theorem can be found in [Lalley Notes] (including Strassen’s theorem in probability) and also equivalence between Hall’s theorem and Strassen’s theorem for finite probability spaces is neatly proved in [Koperberg 2022].