Caltech Logo

Logic Seminar

Wednesday, September 8, 2021
12:00pm to 1:00pm
Add to Cal
Online Event
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.

For more information, please email A. Kechris at kechris@caltech.edu.