On Homomorphism Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914794646274048 |
|---|---|
| author | Brandt, Sebastian Chang, Yi-Jun Grebík, Jan Grunau, Christoph Rozhoň, Václav Vidnyánszky, Zoltán |
| author_facet | Brandt, Sebastian Chang, Yi-Jun Grebík, Jan Grunau, Christoph Rozhoň, Václav Vidnyánszky, Zoltán |
| contents | We introduce a new type 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. The motivation for the construction comes from the adaptation of this method to the LOCAL model of distributed computing. Our approach unifies the previous results in the area, as well as produces new ones. In particular, 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 $\mathbfΣ^1_2$-complete set. This implies a strong failure of Brooks'-like theorems in the Borel context. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_03683 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On Homomorphism Graphs Brandt, Sebastian Chang, Yi-Jun Grebík, Jan Grunau, Christoph Rozhoň, Václav Vidnyánszky, Zoltán Logic Distributed, Parallel, and Cluster Computing Combinatorics We introduce a new type 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. The motivation for the construction comes from the adaptation of this method to the LOCAL model of distributed computing. Our approach unifies the previous results in the area, as well as produces new ones. In particular, 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 $\mathbfΣ^1_2$-complete set. This implies a strong failure of Brooks'-like theorems in the Borel context. |
| title | On Homomorphism Graphs |
| topic | Logic Distributed, Parallel, and Cluster Computing Combinatorics |
| url | https://arxiv.org/abs/2111.03683 |