Borel Matchings and Analogs of Hall's Theorem

Author: Wang, Allison Yiyun

Year: 2020

Degree: Senior thesis (Major)

Advisor: Kechris, Alexander

Committee Members: Kechris, Alexander; Flach, Matthias; Panagiotopoulos, Aristotelis; Tamuz, Omer

Option: Mathematics

DOI: 10.7907/c934-zc02

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.

Files