ON HOMOMORPHISM GRAPHS

We introduce new types of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks [Mar16]. The motivation for the construction comes from the adaptation of this method to the LOCAL model of distributed computing [BCG+21]. Our approach unifies the previous results in the area, as well as produces new ones. In particular, strengthening the main result of [TV21], we show that for Δ>2, it is impossible to give a simple characterization of acyclic Δ-regular Borel graphs with Borel chromatic number at most Δ: such graphs form a Σ 1 2 -complete set. This implies a strong failure of Brooks-like theorems in the Borel context.