UCLA

This dissertation investigates Baire measurable, measurable, and Borel labeling problems in descriptive combinatorics on Borel graphs that are tree-like or grid-like, and also on graphs that have certain expansion behavior.Chapter 2 introduces a framework for applying the determinacy method to prove impossibility results in Borel combinatorics to labeling problems on tree-like graphs and hypergraphs. It also establishes a generalized method of round elimination to prove analogous impossibility results in the theory distributed algorithms and shows that these two methods both naturally apply to the same class of sinkless coloring problems. Chapter 3 provides a proof that the set of games for which a certain player has a winning strategy in a Borel family of games in Baire measurable. This result is used in the previous chapter in the determinacy arguments. This result is proven by classical methods, but it is also shown how the result follows from and fits into the theory of universally Baire sets of reals. Chapter 4 contains joint work with Felix Weilacher and Anton Bernshteyn to find a locally checkable labeling problem on two dimensional grids which can always be solved μ-measurably on any Borel grid for any Borel probability measure μ, but cannot always be solved Baire measurably. Chapter 5 contains joint work with Alexander Kastner to prove that free Borel actions of non-amenable groups admit Baire measurable perfect matchings. Chapter 6 proves an expander mixing lemma for probability measure preserving graphs and uses this result to obtain a simpler construction of an edge-colored highly mixing graph from the descriptive combinatorics literature.