Borel Matchings and Analogs of Hall's Theorem

Borel matchings

Wang, Allison Yiyun ; Kechris, Alexander

University:California Institute of Technology

Department:Physics, Mathematics and Astronomy

关键词: Borel matchings;   

Others  :  https://thesis.library.caltech.edu/13818/7/Wang_Allison_2020.pdf

美国|英语

来源: Caltech THESIS

【 摘 要 】

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.