Borel Matchings and Analogs of Hall's Theorem

Citation

Wang, Allison Yiyun (2020) Borel Matchings and Analogs of Hall's Theorem. Senior thesis (Major), California Institute of Technology. doi:10.7907/c934-zc02. https://resolver.caltech.edu/CaltechTHESIS:06122020-140116149

Abstract

In classical graph theory, Hall’s theorem gives a necessary and sufficient condition for a bipartite graph to have a perfect matching. The analogous statement for Borel perfect matchings is false. If we instead consider Borel perfect matchings almost everywhere or Borel perfect matchings generically, results similar to Hall’s theorem hold. We present Marks’ proof that König’s theorem, a special case of Hall’s theorem, fails in the context of Borel perfect matchings. We then discuss positive results about the existence of Borel matchings that are close to perfect in the measure theory and Baire category settings.

Thesis Files