Complexity of Finite Borel Asymptotic Dimension

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.