Logic Seminar

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.