A Caltech Library Service

Borel Matchings and Analogs of Hall's Theorem


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


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.

Item Type:Thesis (Senior thesis (Major))
Subject Keywords:Borel matchings
Degree Grantor:California Institute of Technology
Division:Physics, Mathematics and Astronomy
Major Option:Mathematics
Awards:Frederic W. Hinrichs, Jr., Memorial Award, 2020. George W. Housner Prize for Academic Excellence and Original Research, 2020. Robert P. Balles Caltech Mathematics Scholar Award, 2020. Herbert J. Ryser Memorial Scholarship, 2020. Fredrick J. Zeigler Memorial Award, 2019. Taussky-Todd Mathematics Prize Fund, 2018.
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Kechris, Alexander
Thesis Committee:
  • Kechris, Alexander
  • Flach, Matthias
  • Panagiotopoulos, Aristotelis
  • Tamuz, Omer
Defense Date:21 May 2020
Record Number:CaltechTHESIS:06122020-140116149
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13818
Deposited By: Allison Wang
Deposited On:15 Jun 2020 17:35
Last Modified:15 Jun 2020 17:35

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page