Logic Colloquium: Finite versus infinite: an insufficient shift

Colloquium | October 6 | 4:10-5 p.m. | 60 Evans Hall

 Yann Pequignot, UCLA

 Department of Mathematics

Analytic sets enjoy a classical representation theorem based on well-founded relations. I will explain a similar representation theorem for Sigma^1_2 sets due to Marcone which is based on an intriguing topological graph: the Shift Graph. The chromatic number of this graph is 2, but its Borel chromatic number is infinite. We use this representation theorem to show that the Shift Graph is not minimal among the graphs of Borel functions which have infinite Borel chromatic number. While this answers negatively the primary outstanding question from (Kechris, Solecki and Todorcevic; 1999), our proof unfortunately does not construct any explicit example of a Borel function whose graph has infinite Borel chromatic number and admits no homomorphism from the Shift Graph.