Complexity of Finite Borel Asymptotic Dimension
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918367676334080 |
|---|---|
| author | Grebík, Jan Higgins, Cecelia |
| author_facet | Grebík, Jan Higgins, Cecelia |
| contents | We show that the set of locally finite Borel graphs with finite Borel asymptotic dimension is $\mathbfΣ^1_2$-complete. The result is based on a combinatorial characterization of finite Borel asymptotic dimension for graphs generated by a single Borel function. As an application of this characterization, we classify the complexities of digraph homomorphism problems for this class of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08797 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of Finite Borel Asymptotic Dimension Grebík, Jan Higgins, Cecelia Logic Combinatorics 03E15 (Primary) 28A05, 05C15 (Secondary) We show that the set of locally finite Borel graphs with finite Borel asymptotic dimension is $\mathbfΣ^1_2$-complete. The result is based on a combinatorial characterization of finite Borel asymptotic dimension for graphs generated by a single Borel function. As an application of this characterization, we classify the complexities of digraph homomorphism problems for this class of graphs. |
| title | Complexity of Finite Borel Asymptotic Dimension |
| topic | Logic Combinatorics 03E15 (Primary) 28A05, 05C15 (Secondary) |
| url | https://arxiv.org/abs/2411.08797 |