Logic Seminar

We construct Borel graphs which settle several questions in descriptive graph combinatorics. These include "Can the Baire measurable chromatic number of a locally finite Borel graph exceed the usual chromatic number by more than one?" and "Can marked groups with isomorphic Cayley graphs have Borel chromatic numbers for their shift graphs which differ by more than one?". As a result, we completely determine the set of pairs (x,y) such that there exists a locally finite Borel graph with usual chromatic number x and Baire measurable chromatic number y.