Department of

March 2018 April 2018May 2018Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu WeThFr Sa 1 2 3 1 2 3 4 5 6 7 1 2 3 4 5 4 5 6 7 8 9 10 8 9 10 11 12 13 14 6 7 8 9 10 11 12 11 12 13 14 15 16 17 15 16 17 18 19 20 21 13 14 15 16 17 18 19 18 19 20 21 22 23 24 22 23 24 25 26 27 28 20 21 22 232425 26 25 26 27 28 29 30 31 29 30 27 28 29 30 31

Tuesday, April 3, 2018

**Abstract:** The Borel chromatic number — introduced by Kechris, Solecki, and Todorcevic (1999) — generalizes the chromatic number on finite graphs to definable graphs on topological spaces. 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, our understanding is actually very poor.

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 explain why the answer is negative using a representation theorem for $\Sigma^1_2$ sets due to Marcone.