Effectivization in Borel Combinatorics
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.