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, Φ. An effectivization theorem for Φ says that any (lightface) Δ11 graph with a Borel witness to Φ in fact has a Δ11 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.