论文标题
可计算与树木本地问题的描述性组合学
Computable vs Descriptive Combinatorics of Local Problems on Trees
论文作者
论文摘要
我们研究了ARXIV中开发的“常见位置理论”中可计算设置的位置，用于$δ$ regular-regular-regular trees，$δ\ inω$的局部问题。我们表明，当且仅当它在每个Borel $δ$ groumard Forest上接受baire可测量的解决方案时，就会在每个高度可计算的$δ$ grounder森林上接受可计算的解决方案。我们还表明，如果这样的问题在每个可计算的最大程度$δ$森林上都接受了可计算的解决方案，那么它将在每个最高度$δ$ borel图上都有一个连续的解决方案，并具有适当的拓扑假设，尽管相反的情况不存在。
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.
