Caltech Home > PMA Home > Calendar > Logic Seminar
Wednesday, September 08, 2021
12:00 PM - 1:00 PM
Online Event

# Logic Seminar

New examples of bounded degree acyclic graphs with large Borel chromatic number
Zoltán Vidnyánszky, Department of Mathematics, Caltech,

Marks proved the existence of dd-regular acyclic Borel graphs with Borel chromatic number d+1d+1. It can be shown that such statements cannot be proved using measures or Baire category, and, indeed, the Borel determinacy theorem had to be invoked. We discuss a generalization of Marks' method, which leads to an interesting new class of examples of 33-regular acyclic Borel graphs, which we call homomorphism graphs. This yields new proofs of a number of known results. As a new application, we show that it is hard to decide whether the Borel chromatic number of a Borel graph is ≤3≤3, even for acyclic 33-regular graphs (that is, such graphs form a Σ12Σ21-complete set).
Joint work with Jan Grebík.