Kurt Gödel Research Center

2018 seminar talk: Borel chromatic numbers: basis and antibasis results

Talk held by Zoltán Vidnyánszky (KGRC) at the KGRC seminar on 2018-06-14.

Abstract

We give a full description of the existence of a homomorphism basis for Borel graphs of given Borel chromatic number. In particular, we show that there is a Borel graph with Borel chromatic number 3 that admits a homomorphism to any Borel graph of Borel chromatic number at least 3. We also discuss the relation of these results to Hedetniemi's conjecture.