UCLA

This dissertation concentrates on two prominent lines of research in modern descriptive set theory: Descriptive combinatorics and the theory of definable equivalence relations.Chapter 2 is focused on a body of results related to Brooks’s theorem, a fundamental graph theory result that characterizes the graphs of maximum degree d having chromatic number at most d. Measurable versions of Brooks’s theorem, as well as definable versions of a similar result on list coloring known as Gallai’s theorem, are surveyed in Section 2.2. Classical results that extend Brooks’s theorem and Gallai’s theorem to directed graphs are also discussed in Section 2.3. The chapter culminates in the proofs of both a definable version of Gallai’s theorem for directed graphs and a measurable version of Brooks’s theorem for directed graphs in Section 2.4. In the final two sections, potential connections with Johansson’s theorem and the theory of LOCAL algorithms are explored.Chapter 3 contains joint work with Jan Grebík on the projective complexity of finite Borel asymptotic dimension. The chapter begins with an overview of the study of countable Borel equivalence relations, followed by a survey of open problems related to the well-known question of whether the set of Borel codes of hyperfinite equivalence relations is Σ1/2 -complete. An overview of Borel asymptotic dimension and the role it plays in the study of hyperfiniteness is provided in Sections 3.3 and 3.4. The main theorem that the set of Borel codes of locally finite Borel graphs having finite Borel asymptotic dimension is Σ1/2 -complete is described in Section 3.5. The chapter concludes with a brief section concerning potential extensions to the study of Borel semigroup actions.