We investigate the problem of what equivalence relations from recursion theory are universal countable Borel equivalence relations. While this question is interesting in its own right, it has also been a particularly rich source of connections between recursion theory, countable Borel equivalence relations, and Borel combinatorics. Tools developed by this investigation have proved very applicable to other problems in these fields.

In Chapter 2, we prove a model universality theorem, and introduce several themes of the thesis. A corollary of this first theorem is that polynomial time Turing equivalence is a universal countable Borel equivalence relation.

Slaman and Steel have shown that arithmetic equivalence is a universal countable Borel equivalence relation. In Chapter 3, we combine this fact with the existence of a cone measure for arithmetic equivalence to prove several structural results about universal countable Borel equivalence relations in general. We show that universality for Borel reductions coincides with universality for Borel embeddings, and a universal countable Borel equivalence relation is always universal on some nullset with respect to any Borel probability measure. We also settle questions of Thomas, and Jackson, Kechris, and Louveau by showing that a smooth disjoint union of non-universal countable Borel equivalence relations is non-universal. This result can be significantly strengthened by assuming a conjecture of Martin which states that every Turing invariant function is equivalent to a uniformly Turing invariant function on a Turing cone.

In Chapter 4, we investigate uniformity of homomorphisms among equivalence relations from recursion theory. We pose several open questions in this context, and investigate the implications of the uniformity that they imply. We introduce the concept of a Borel metric on a countable Borel equivalence relation, and show that this concept is closely connected to a weakening of the notion of a uniform homomorphism. Using this language of metrics and the machinery of Slaman and Steel for proving the universality of arithmetic equivalence, we construct an example of a homomorphism between equivalence relations coarser than Turing equivalence which is not uniform on any pointed perfect set. This is the first example of a nonuniform homomorphism in this sort of recursion-theoretic context, and it places some limits on how abstract a proof of Martin's conjecture could be.

In Chapter 5, we turn to the question of whether recursive isomorphism is a universal countable Borel equivalence relation. Improving prior results of Dougherty and Kechris and Andretta, Camerlo, and Hjorth, we show that recursive isomorphism on $3^\omega$ is a universal countable Borel equivalence relation. We isolate a question of Borel combinatorics for which a positive answer would imply that recursive isomorphism on $2^\omega$ is universal. We show that this question is equivalent to the problem of whether $\omega$ many 2-regular Borel graphs on the same space can be simultaneously Borel 3-colored so that there are no monochromatic points. We then show that this question has an affirmative answer if and only if many-one equivalence on $2^\omega$ is a uniformly universal countable Borel equivalence relation. Thus, we have an exact combinatorial calibration of the difficulty of this universality problem.

In Chapter 6, we consider the question of whether there exist disjoint Borel complete sections for every pair of aperiodic countable Borel equivalence relations. We show that this question is very robust, and has many equivalent formulations. A positive answer to this question would positively answer the combinatorial question of the previous paragraph, while a negative answer would settle several open questions of Borel combinatorics. We also show that this question is true in both the measure and category context, in all its equivalent forms. One application of this fact is that every Borel bipartite 3-regular graph has measurable and Baire measurable edge colorings with 4 colors. This is a descriptive analogue of a special case of Vizing's theorem on edge colorings from classical combinatorics. Finally, we see that recursive isomorphism on $2^\omega$ is measure universal. Thus, purely measure-theoretic tools cannot be used to prove that it is not universal.

We explore the descriptive set theory of problems originating in theoretical computer science. We investigate a few special cases of locally checkable labelling problems using a variety of Borel and measurable techniques. Our result clarifies a small part of the connection between descriptive set theory and distributed computing. And, we adapt tools from the algebraic approach to constraint satisfaction problems to the Borel setting. In particular we draw a direct connection between NP-completeness and $\mathbf{\Sigma}^1_2$-completeness.

We develop a relationship between Borel equivalence relations and weak choice principles. Specifically, we show that questions about Borel reducibility and strong ergodicity between equivalence relations which are classifiable by countable structures can be translated to questions about fragments of choice holding in certain symmetric models. We then use tools developed in the '60s and '70s to analyze such symmetric models and solve several problems about Borel equivalence relations.

This relationship is explained in Chapter~\ref{chapter:symmetric-models-borel-reducibility}.

These techniques are applied to the study of equivalence relations high in the Borel reducibility hierarchy in Chapter~\ref{chapter:jumps-HKL}.

In \cite{HKL98} Hjorth, Kechris and Louveau refined the Friedman-Stanley jump hierarchy by defining equivalence relations $\cong^\ast_{\alpha+1,\beta}$, $\beta<\alpha$.

For example, they show that $\cong^\ast_{\omega+1,<\omega}$ provides invariants for $\Sigma^0_{\omega+1}$ equivalence relations induced by actions of $S_\infty$, while $\cong^\ast_{\omega+1,0}$ provides invariants for $\Sigma^0_{\omega+1}$ equivalence relations induced by actions of \textit{abelian} closed subgroups of $S_\infty$.

Whether $\cong^\ast_{\omega+1,0}$ is strictly below $\cong^\ast_{\omega+1,<\omega}$ in Borel reducibility was left open.

We show that they are distinct and prove generally that the entire hierarchy defined by Hjorth-Kechris-Louveau is strict, establishing their conjecture.

We further study the Friedman-Stanley jumps. For example, we find an equivalence relation $F$ on a Polish space $Y$ such that $F$ is Borel bireducible with $=^{++}$ and $F\rest C$ is Borel bireducible with $=^{++}$ for any non-meager set $C\subset Y$. This answers a question of Zapletal, arising from the results of Kanovei-Sabok-Zapletal \cite{ksz}. In the terminology of \cite{ksz}, the result states ``$=^{++}$ is in the spectrum of the meager ideal''.

For these proofs we analyze the symmetric models $M_n$, $n<\omega$, developed by Monro \cite{Mon73} to separate Kinna-Wagner principles. We extend Monro's construction past $\omega$, through all countable ordinals, answering a question of Karagila \cite{Kar17}.

Chapter \ref{chapter:products-ctbl-relations} is devoted to study equivalence relations lower in the hierarchy, ``just above'' the countable products of countable Borel equivalence relations.

We show that for a countable Borel equivalence relation $E$, if $E$ is strongly ergodic with respect to a measure $\mu$ then $E^\N$ is strongly ergodic with respect to $\mu^\N$.

Similarly we establish strong ergodicity results between the recently defined $\Gamma$-jumps of Clemens and Coskey \cite{CC19}. In particular, we show that the $\mathbb{F}_2$-jump of $E_\infty$ is strictly above the $\mathbb{Z}$-jump of $E_\infty$, answering a question of Clemens and Coskey.

We study a notion of equivalence relations which can be classified by infinite sequences of ``definably countable sets''.

In particular, we define an interesting example of such equivalence relation which is strictly above $E_\infty^\N$, strictly below $=^+$, and is incomparable with the $\Gamma$-jumps of countable equivalence relations.

The proofs rely on a fine analysis of the very weak choice principles ``every sequence of $E$-classes admits a choice sequence'', for various countable Borel equivalence relations $E$.

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.