Invariant Combinatorics on Borel Equivalence Relations

Citation

Wolman, Michael Solomon (2025) Invariant Combinatorics on Borel Equivalence Relations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/w4nq-ag86. https://resolver.caltech.edu/CaltechTHESIS:06022025-192005565

Abstract

This thesis comprises four independent parts and an appendix.

1. We define and study expansion problems on countable structures in the setting of descriptive combinatorics. We consider both expansions on countable Borel equivalence relations and on countable groups, in the Borel, measure, and category settings, and establish some basic correspondences between the two notions. We then explore in detail many examples, including finding spanning trees in graphs, finding monochromatic sets in Ramsey's Theorem, and linearizing partial orders.

2. Standard results in descriptive set theory provide sufficient conditions for a set P ⊆ ℕ^ℕ × ℕ^ℕ to admit a Borel uniformization, namely, when P has small or large sections. We consider an invariant analogue of these results with respect to a Borel equivalence relation E. Given E, we show that every such P admits an E-invariant Borel uniformization if and only if E is smooth. We also compute the definable complexity of counterexamples in the case where E is not smooth, using category, measure, and Ramsey-theoretic methods. We also show that the set of pairs (E, P) such that P has large sections and admits an E-invariant Borel uniformization is Σ¹₂-complete.

3. Let E, F be Borel equivalence relations on X, Y, and P be an E-invariant Borel set whose sections contain countably many F-classes. We explore obstructions to the existence of Borel E-invariant uniformizing sets for P, i.e., sets choosing one F-class from every section. We survey known results, and prove new dichotomies for the case where P has σ-bounded finite sections. On the way, we prove a dichotomy characterizing the essential values of Borel cocycles into residually finite Polish groups.

4. We show that the Kechris–Solecki–Todorčević dichotomy implies the Harrington–Kechris–Louveau dichotomy. We also give a simple proof of a graph-theoretic dichotomy of Miller for doubly-indexed sequences of analytic graphs, and show that this dichotomy generalizes to finite-dimensional hypergraphs but not to ℵ₀-dimensional hypergraphs.

5. An effective version of Nadkarni’s Theorem was proved in Ditzen’s unpublished Ph.D. thesis. The appendix contains a streamlined exposition of the proof and provides an alternative proof of the Effective Ergodic Decomposition Theorem for invariant measures (also originally proved by Ditzen). In addition, we show that the existence of an invariant Borel probability measure is not effective.

Thesis Files