Complexity of finite Borel asymptotic dimension
Abstract
Abstract We show that the set of locally finite Borel graphs with finite Borel asymptotic dimension is $\boldsymbol {\Sigma }^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.
Fields of Study & Subjects
Advanced Topology and Set Theory
Mathematical Dynamics and Fractals
Analytic Number Theory Research
Publication details
- Journal / source
- Forum of Mathematics Sigma
- Volume
- 14
- Publication date
- 1 January 2026
- Language
- EN