Publication details
ON HOMOMORPHISM GRAPHS
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Periodical |
| Magazine / Source | FORUM OF MATHEMATICS PI |
| MU Faculty or unit | |
| Citation | |
| web | https://www.cambridge.org/core/journals/forum-of-mathematics-pi/article/on-homomorphism-graphs/A01614AEBBBD2869DD34AA7C430BF39E |
| Doi | https://doi.org/10.1017/fmp.2024.8 |
| Keywords | 3e+15; 05C15; 28A05 |
| Description | 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 Delta > 2, it is impossible to give a simple characterization of acyclic Delta-regular Borel graphs with Borel chromatic number at most Delta: such graphs form a Sigma(1)(2)-complete set. This implies a strong failure of Brooks-like theorems in the Borel context. |