UCLA

This dissertation investigates Borel graphs on Polish spaces. It explores two main directions: the relationship between a Borel graph's geometry and its measurable properties, and the projective complexity of labeling problems in Borel combinatorics.

Chapter 2 contains joint work with Clark Lyons on the Baire measurable combinatorics of Borel graphs with non-amenable connected components. In this setting, we show that a Baire measurable perfect matching exists when the graph is vertex transitive, and that a Baire measurable balanced orientation exists when all degrees are even.

Chapter 3 presents a proof that Borel graphs of subexponential growth are measure hyperfinite, and includes a discussion of recent advances concerning hyperfiniteness under growth rate constraints.

Chapter 4 introduces a problem of Kechris and Chen about the $\sigma$-structurability of compressible countable Borel equivalence relations. We provide a proof in non-probabilistic language that a locally finite vertex transitive connected graph has a realization as a probability-measure-preserving graph if and only if it is unimodular. We also generalize this result to the case of countable relational structures with compact stabilizers.

Chapter 5 explores the projective complexity of characterizing which Borel graphs admit Borel solutions to labeling problems. We introduce a formal notion of gadget reduction and use this notion to lift NP-completeness results in finite combinatorics to $\mathbf{Sigma}^1_2$-completeness results for their Borel analogues. We then give several concrete examples where this idea is applied.

Chapter 6 contains joint work with Clark Lyons to provide a classical proof that for a Borel family of games, the set of games where player II wins is Baire measurable, universally measurable, and Ramsey measurable.