Finite versus infinite: an insufficient shift
The Borel chromatic number – introduced by Kechris, Solecki, and Todorcevic (1999) – generalizes the chromatic number to Borel graphs. While the G_0 dichotomy states that there exists a minimal graph with uncountable Borel chromatic number, it turns out that characterizing when a graph has infinite Borel chromatic number is far more intricate. Even in the case of graphs generated by a single function, the situation is quite complicated. The Shift Graph on the space of infinite subsets of natural numbers is generated by the function that removes the minimum element. It is acyclic but has infinite Borel chromatic number. In 1999, Kechris, Solecki, and Todorcevic asked whether the Shift Graph is minimal among the graphs generated by a single Borel function that have infinite Borel chromatic number. I will sketch a proof that the answer is negative using descriptive complexity considerations and a representation theorem for Sigma^1_2 sets due to Marcone (1994). This result has recently been considerably strengthened by Todorcevic and Vidnyanszky who proved that the set of closed subsets of the Shift Graph that have infinite Borel Chromatic number is Pi^1_2 complete, therefore ruling out most interesting basis results for this class of Borel graphs.