Effectivization in Borel Combinatorics
Speaker:
Riley Thornton, University of California, Los Angeles
Date and Time:
Friday, June 25, 2021 - 1:30pm to 3:00pm
Location:
Online
Abstract:
In Borel combinatorics, we often want to know when a Borel graph (or equivalence relation, quasi-order, etc) admits a Borel witness to some combinatorial property, $\Phi$. An effectivization theorem for $\Phi$ says that any (lightface) $\Delta^1_1$ graph with a Borel witness to $\Phi$ in fact has a $\Delta^1_1$ witness. This kind of effectivization gives a strong upper bound on the projective complexity of the set of graphs where a definable witness exists and suggests that such graphs might admit a nice structural characterization. This talk will present a streamlined method for proving effectivization theorems, give a number of applications, and discuss some related dichotomy theorems.