A wide range of problems in computer science, including constraint satisfaction, can be framed in the language of graph homomorphisms. There are problems for which the existence of a solution may be proved by means of the Axiom of Choice or a non-principal ultrafilter. Although such solutions exist abstractly, in practice we want solutions that are definable, and so it is natural to impose restrictions. Interestingly, this often makes the problems harder to solve, but the solutions have a concrete description. This thesis studies the cost of insisting on definable solutions. The parallel between computer-science and set-theoretic complexity is a recurring theme in the thesis.
Descriptive set theory provides the language for all three substantive chapters: Borel definability for Chapter 2, the Baire-class hierarchy for Chapter 3, and Polish group actions for Chapter 4.
The complete LaTeX sources are available on GitHub. The thesis uses the ut-thesis document class together with my own style files.
2026 © Tonatiuh Matos Wiederhold