UCLA

This dissertation examines the effective theory of Borel graph combinatorics and analytic equivalence relations, as well as the theory of recursive Polish spaces.

In Chapter 2, the effective combinatorics of graphs is studied, with an interest both in situations in which the existence of Borel combinatorial objects guarantee the existence of the corresponding effectively Borel objects, and in situations in which Borel constructions do not completely effectivize. We establish the basic properties of graphs in which all $\Delta^1_1$ sets of vertices have $\Delta^1_1$ boundaries in the graph and, moreover, in which we can effectively obtain codes for the boundaries of $\Delta^1_1$ set of vertices. It is then proven that if such a graph admits a countable $\Delta^1_1$-coloring, then the graph has a $\Delta^1_1(\mathcal{O})$ maximal independent set. It is shown that $\mathcal{O}$ is the optimal parameter for the continuous homomorphism of $G_0$ into a graph which is not countably $\Delta^1_1$-colorable, which is guaranteed to exist by the $G_0$-dichotomy \cite{kst_1999}. The relationship between finite Borel colorings and finite $\Delta^1_1$ colorings is studied. Building upon work of Louveau \cite{louveau}, it is proven that Borel $2$-colorability implies $\Delta^1_1$ $2$-colorability for $\Sigma^1_1$ graphs, a result that has applications to the combinatorics of $2$-regular $\Delta^1_1$ graphs. Using a graph from \cite{todorcevic_2018}, it is shown that a $\Delta^1_1$ graph with Borel chromatic number $k\in \{3, 4, \dots\}$ could have as its $\Delta^1_1$ chromatic number any element of $\{k, k+1, \cdots, \aleph_0\}$.

Chapter 3 is focused on analytic equivalence relations. Using effective methods, an example is given of an analytic equivalence relation which is not the connectedness relation of a Borel graph. It is also shown that there is a $\Sigma^1_1$ equivalence relation which is the connectedness relation of a Borel graph, but is not the connectedness relation of a $\Delta^1_1$ graph. The notion of a $\bfpc{\Sigma}^1_1$-ranked equivalence relation is introduced, which is a notion of a definable ranking for the classes of an analytic equivalence relation with $\omega_1$-many classes. It is proved that there are no almost Borel reductions from an analytic equivalence relation, all of whose classes are Borel, to a $\bfpc{\Sigma}^1_1$-ranked equivalence relation, generalizing a fact about almost Borel reductions to $E_{\omega_1}$. Several analytic equivalence relations are then proven to be $\bfpc{\Sigma}^1_1$-ranked.

Some foundational questions regarding recursive Polish spaces are addressed in Chapter 4. It is shown that there is a recursive Polish space $\mathcal{X}$ whose frame, i.e., the collection of effectively open subsets of $\omega\times \mathcal{X}$, is not determined by the effectively open subsets of $\mathcal{X}$. Some results regarding recursive subspaces of the Baire space are proved, including a characterization of the effectively closed subsets of Baire space which are recursive subspaces. Finally, a familiar representation theorem for effectively Borel subset of Baire space is extended to all recursive Polish spaces.