Informace o publikaci
ON HOMOMORPHISM GRAPHS
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | FORUM OF MATHEMATICS PI |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://www.cambridge.org/core/journals/forum-of-mathematics-pi/article/on-homomorphism-graphs/A01614AEBBBD2869DD34AA7C430BF39E |
| Doi | https://doi.org/10.1017/fmp.2024.8 |
| Klíčová slova | 3e+15; 05C15; 28A05 |
| Popis | 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. |