CaltechTHESIS
A Caltech Library Service

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 Σ 1 2 -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 ℵ 0 -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.

Item Type: Thesis (Dissertation (Ph.D.))
Subject Keywords: descriptive set theory; logic; Borel; group; descriptive combinatorics; expansions; uniformization; effective descriptive set theory; invariant descriptive set theory; dichotomy; Borel cocycle; essential value
Degree Grantor: California Institute of Technology
Division: Physics, Mathematics and Astronomy
Major Option: Mathematics
Awards: Apostol Award for Excellence in Teaching in Mathematics, 2024.
Thesis Availability: Public (worldwide access)
Research Advisor(s):
  • Kechris, Alexander S. (co-advisor)
  • Tamuz, Omer (co-advisor)
Thesis Committee:
  • Hutchcroft, Thomas (chair)
  • Ervin, Garrett
  • Kechris, Alexander S.
  • Tamuz, Omer
Defense Date: 28 May 2025
Funders:
Funding Agency Grant Number
Fonds de Recherche du Quebec - Nature et Techonologies 290736
NSF Division of Mathematical Sciences 1950475
Record Number: CaltechTHESIS:06022025-192005565
Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:06022025-192005565
DOI: 10.7907/w4nq-ag86
Related URLs:
URL URL Type Description
https://doi.org/10.48550/arXiv.2505.04130 arXiv Article adapted for ch. 2
https://doi.org/10.48550/arXiv.2405.15111 arXiv Article adapted for ch. 3
https://michael.wolman.ca/papers/effective_nadkarni.pdf Related Document Article adapted for appendix
ORCID:
Author ORCID
Wolman, Michael Solomon 0009-0001-6062-4128
Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code: 17371
Collection: CaltechTHESIS
Deposited By: Michael Wolman
Deposited On: 03 Jun 2025 19:24
Last Modified: 10 Jun 2025 19:56

Thesis Files

[img] PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page