Logic Seminar
Please note that the time is PST
The shift graph GS on the infinite subsets of the naturals has been introduced by Kechris-Solecki-Todorcevic, alongside with the graph G0. Since then, it has become an important (and essentially unique) tool to establish complexity results concerning Borel coloring problems.
In this talk, we show that much like G0, this graph is rather canonical. First, surprisingly, every acyclic Borel graph given by a function admits a Borel homomorphism to GS. Second, I will discuss that while a G0-like dichotomy in the Borel context is not possible by complexity results, considering more relaxed versions of coloring could allow for positive results in the case of GS and even general coloring problems. Joint work with Balazs Bursics and Anett Kocsis.