David Chodounský (Czech Academy of Sciences) – Games and chromatic numbers of definable graphs

A graph has a countable chromatic number if the vertices can be labeled by natural numbers so that no edge has the same label on both ends. Verifying this property for a given graph can be somewhat difficult; consider e.g. the graph of points in the Euclidean space $ℝ^n$ connected with an edge iff their distance is a rational number. The countable chromatic number of this graph is an easy observation for $n=1$, but a nontrivial result for $n>1$ (Komjath, Schmerl). I will introduce an infinite determined game which provides a simple criterion for a definable (analytic on a Polish space) graph to be countably chromatic; it is sufficient to verify that the second player has a winning strategy. Using this criterion we can e.g. easily resolve the example of $ℝ^n$, as well as deduce interesting consequences on the structure of uncountably chromatic definable graphs.

The talk is based on the paper Chodounský, Zapletal: Two graph games (2024).