Computable vs Descriptive Combinatorics of Local Problems on Trees
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908854867984384 |
|---|---|
| author | Weilacher, Felix |
| author_facet | Weilacher, Felix |
| contents | We study the position of the computable setting in the "common theory of locality" developed in arXiv:2106.02066 and arXiv:2204.09329 for local problems on $Δ$-regular trees, $Δ\in ω$. We show that such a problem admits a computable solution on every highly computable $Δ$-regular forest if and only if it admits a Baire measurable solution on every Borel $Δ$-regular forest. We also show that if such a problem admits a computable solution on every computable maximum degree $Δ$ forest then it admits a continuous solution on every maximum degree $Δ$ Borel graph with appropriate topological hypotheses, though the converse does not hold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_06689 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Computable vs Descriptive Combinatorics of Local Problems on Trees Weilacher, Felix Logic Combinatorics 05C15 (Primary) 03E15, 03D45 We study the position of the computable setting in the "common theory of locality" developed in arXiv:2106.02066 and arXiv:2204.09329 for local problems on $Δ$-regular trees, $Δ\in ω$. We show that such a problem admits a computable solution on every highly computable $Δ$-regular forest if and only if it admits a Baire measurable solution on every Borel $Δ$-regular forest. We also show that if such a problem admits a computable solution on every computable maximum degree $Δ$ forest then it admits a continuous solution on every maximum degree $Δ$ Borel graph with appropriate topological hypotheses, though the converse does not hold. |
| title | Computable vs Descriptive Combinatorics of Local Problems on Trees |
| topic | Logic Combinatorics 05C15 (Primary) 03E15, 03D45 |
| url | https://arxiv.org/abs/2208.06689 |