Complexity of Finite Borel Asymptotic Dimension

Abstract

We show that the set of locally finite Borel graphs with finite Borel asymptotic dimension is ${\mathbf{\Sigma }}_2^1$-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.

18 pages

References in corpus (3)

• Homology and topological full groups of etale groupoids on totally disconnected spaces
• A determinacy approach to Borel combinatorics
• Hyperfiniteness and Borel combinatorics