Complexity of Finite Borel Asymptotic Dimension

This paper establishes that the set of locally finite Borel graphs with finite Borel asymptotic dimension is $\mathbf{\Sigma}^1_2$-complete by providing a combinatorial characterization for graphs generated by a single Borel function, which is subsequently used to classify the complexities of digraph homomorphism problems within this class.

The Gist

Imagine you are a city planner trying to organize a massive, infinite city. This city isn't made of streets and buildings, but of points (people) and connections (relationships). In math, this is called a Borel graph.

The paper by Jan Grebík and Cecelia Higgins tackles a very specific, high-level question: How do we measure the "complexity" of organizing this infinite city, and how hard is it to tell if a city can be organized efficiently?

Here is the breakdown using simple analogies.

1. The Big Picture: The "Infinite City" Problem

Imagine you have a city where every person has a list of neighbors. Some cities are simple; you can break them down into small, manageable neighborhoods. Others are chaotic and tangled.

Mathematicians have a concept called Asymptotic Dimension. Think of this as a measure of how "spread out" or "cluttered" the city is.

• Low Dimension: The city is like a flat sheet of paper. You can cover it with a few layers of transparent sheets, and the people on any single sheet don't get too far apart.
• High Dimension: The city is like a tangled ball of yarn. No matter how you try to cover it, the connections get messy and stretch out infinitely.

The authors are asking: "Is it easy or impossible to tell if a given infinite city has a 'low dimension' (is well-organized)?"

2. The Main Discovery: The "Impossible to Solve" Puzzle

The paper proves that figuring out if a city has a "low dimension" is a Σ₁²-complete problem.

What does that mean in plain English?
In the world of logic and computer science, problems are ranked by how hard they are to solve.

• Easy: "Is this number even?"
• Hard: "Can this maze be solved?"
• Impossible (in a specific way): "Does a solution exist for any possible rule set?"

The authors show that checking for "finite Borel asymptotic dimension" is at the very top of the "hard" pile. It is maximally complex.

• The Analogy: Imagine a detective trying to solve a crime. If the crime is "low dimension," the detective can solve it with a standard checklist. If the crime is "maximally complex," the detective would need to check every possible universe to be sure. The paper proves that for these specific infinite cities, you are stuck in that "check every universe" scenario. You can't simplify the test.

3. The Secret Weapon: The "Forward-Independent" Hitting Set

To prove this, the authors found a clever shortcut. They realized that for a specific type of city (one generated by a single rule, like "everyone points to the next person in line"), the "dimension" problem is actually the same as a game called "The Forward-Independent Hitting Set."

The Game Analogy:
Imagine a game where you have an infinite line of people.

1. The Rule: Everyone points to the next person.
2. The Goal: You need to pick a group of people (a "Hitting Set") such that:
   • Hitting: If you start anywhere, you will eventually run into someone in your group.
   • Forward-Independent: If you pick a person, you cannot pick anyone they point to for the next $r$ steps. There must be a "buffer zone" of non-members.

The Breakthrough:
The authors proved:

• If you can play this game successfully for any distance $r$, the city is "well-organized" (low dimension).
• If you cannot play this game, the city is "chaotic."

This turned a geometric problem (measuring distance in a city) into a combinatorial game (picking people in a line). This game is the key to the complexity.

4. The Application: The "Homomorphism" Puzzle

The paper also applies this logic to a different problem: Graph Homomorphisms.

The Analogy:
Imagine you have a complex city (the input) and a tiny, simple model city (the template, $H$). You want to know: "Can I map every person in the big city to a person in the model city without breaking the rules of who is connected to whom?"

This is a classic computer science problem called CSP (Constraint Satisfaction Problem).

• The Twist: The authors looked at this for infinite cities with specific rules.
• The Result: They classified exactly when this mapping is "easy" (you can do it) and when it is "impossible" (the set of solvable cases is maximally complex).
  • If the model city has a "loop" (a person pointing to themselves), it's easy.
  • If the model city is "ergodic" (everyone can eventually reach everyone else in a cycle) but has no loops, it's maximally complex.
  • If the model city is broken into disconnected pieces, it's "easy" (in a different, simpler way).

5. Why Should You Care?

This might sound abstract, but it connects to real-world computing and logic:

• Distributed Computing: The paper mentions the LOCAL model, which is how computers in a network talk to each other to solve problems (like coloring a map so no neighbors have the same color).
  • The authors found a link: If a problem is "easy" to solve in a distributed network (fast communication), it corresponds to a "maximally complex" logic puzzle in the infinite world.
  • If a problem is "hard" to solve in a network (takes forever), the logic puzzle is actually "simple" to check.
• The Boundary of Knowledge: It tells us where the limits of mathematical proof lie. It says, "Here is a specific type of structure where we can never find a simple formula to check if it's 'nice' or 'messy.' We have to accept that it is inherently complex."

Summary

The paper is like a map of a mountain range.

1. The Mountain: The complexity of organizing infinite networks.
2. The Summit: The authors proved that checking if a network is "well-organized" is the hardest possible task in its category.
3. The Path: They found a secret trail (the "Forward-Independent Hitting Set" game) that leads straight to the summit.
4. The View: From the top, they looked down and saw how this complexity affects other problems, like mapping cities and distributed computing, showing us exactly which problems are solvable and which are forever out of reach.

Technical Summary

1. Problem Statement and Context

The paper addresses the descriptive set-theoretic complexity of Borel hyperfiniteness and its relationship to Borel asymptotic dimension.

• Background: A Borel graph $G$ is Borel hyperfinite if it is the countable increasing union of Borel graphs with finite connected components. The complexity of the set of codes for Borel hyperfinite graphs is a major open problem; it is known to be $\Sigma^1_2$ (analytic), but it is unknown if it is $\Sigma^1_2$-complete (maximally complex within the projective hierarchy).
• Motivation: Recent work by Conley, Gao, Miller, and others introduced Borel asymptotic dimension ($\text{asdim}_B$) as a tool to study hyperfiniteness. It was proven that if a locally finite Borel graph has finite $\text{asdim}_B$, it is Borel hyperfinite.
• Core Question: What is the exact complexity of the set of locally finite Borel graphs with finite Borel asymptotic dimension? The authors aim to determine if this set is $\Sigma^1_2$-complete, which would imply that finite Borel asymptotic dimension is a "hard" property to verify, similar to hyperfiniteness.

2. Methodology

The authors employ a combination of descriptive set theory, combinatorial graph theory, and measurable dynamics.

• Reduction to Single-Function Graphs: The authors focus on graphs generated by a single Borel function $f: X \to X$ (denoted $G_f$). They restrict attention to acyclic functions (where $f^k(x) \neq x$ for all $k \geq 1$).
• Combinatorial Characterization: They establish a bridge between the geometric notion of asymptotic dimension and a purely combinatorial property: the existence of forward-independent hitting sets.
  • A set $H$ is a hitting set if every orbit eventually enters $H$.
  • $H$ is $r$-forward-independent if no point in $H$ maps back to $H$ within $r$ steps.
• Complexity Framework: They utilize the projective hierarchy ($\Sigma^1_2$ and $\Pi^1_1$). To prove $\Sigma^1_2$-completeness, they use a general theorem by Frisch, Shinko, and Vidnyánszky [FSV24], which reduces the problem to constructing a specific Borel structure on the space of infinite subsets of $\mathbb{N}$ ($[\mathbb{N}]^\mathbb{N}$) that admits homomorphisms to a target structure only under specific conditions.
• Shift Graph Construction: The proof relies heavily on the shift graph $G_S$ on $[\mathbb{N}]^\mathbb{N}$ (generated by the shift map $S(x)(n) = x(n+1)$). They construct a family of functions parameterized by $\sigma \in \mathbb{N}^\mathbb{N}$ such that the existence of a homomorphism (or hitting set) depends on the "dominating" properties of $\sigma$.

3. Key Contributions and Results

A. Characterization of Finite Borel Asymptotic Dimension (Theorem 1.2)

The authors prove a combinatorial characterization for graphs generated by a single acyclic Borel function $f$:
The following are equivalent:

1. $\text{asdim}_B(G_f)$ is finite.
2. $\text{asdim}_B(G_f) = 1$.
3. For every $r \in \mathbb{N}^+$, there exists a Borel $r$-forward-independent hitting set for $f$.

Significance: This result is surprising because it shows that for this specific class of graphs, having finite asymptotic dimension is equivalent to having dimension exactly 1. It reduces a geometric covering problem to the existence of specific hitting sets.

B. Complexity of Finite Borel Asymptotic Dimension (Theorem 1.1)

Main Result: The set of locally finite Borel graphs having finite Borel asymptotic dimension is $\Sigma^1_2$-complete.

• Implication: This is the first natural geometric property of Borel graphs proven to be $\Sigma^1_2$-complete. It suggests that determining finite Borel asymptotic dimension is as hard as the hardest problems in the analytic hierarchy.
• Method: They construct a specific Borel function $f$ on a product space such that the set of parameters $\sigma$ for which $f_\sigma$ admits $r$-forward-independent hitting sets for all $r$ is $\Sigma^1_2$-complete.

C. Classification of Digraph Homomorphism Problems (Theorem 1.4)

The authors classify the complexity of the Borel Constraint Satisfaction Problem (CSP) for digraphs generated by a single Borel function, denoted $\text{CSP}^{\text{function}}_B(H)$, where $H$ is a finite sinkless digraph.
The complexity depends on the structure of $H$:

1. If $H$ contains a loop: $\text{CSP}^{\text{function}}_B(H)$ is $\Pi^1_1$ (co-analytic). In fact, it contains all such digraphs.
2. If $H$ is ergodic and loopless: $\text{CSP}^{\text{function}}_B(H)$ is $\Sigma^1_2$-complete.
   • Ergodicity here means the digraph contains a strongly connected component where paths of all sufficiently large lengths exist between any two vertices.
3. If $H$ is not ergodic: $\text{CSP}^{\text{function}}_B(H)$ is $\Pi^1_1$.

Connection to Distributed Computing: This classification mirrors the complexity of Locally Checkable Labeling (LCL) problems in the LOCAL model of distributed computing.

• $\Sigma^1_2$-complete cases correspond to problems solvable in $O(\log^* n)$ rounds (e.g., 3-coloring).
• $\Pi^1_1$ cases correspond to problems requiring linear time or being impossible to solve efficiently (e.g., 2-coloring).

4. Technical Mechanisms

• Forward-Independent Hitting Sets: The core technical innovation is linking the existence of these sets to the complexity of the problem. They show that while the shift graph $G_S$ on the whole space $[\mathbb{N}]^\mathbb{N}$ does not admit such sets, it does admit them on "non-dominating" subsets. This dichotomy allows them to encode the $\Sigma^1_2$ condition.
• Homomorphism to $D_r$: They define a target digraph $D_r$ on $\mathbb{N}$ where edges represent a "countdown" of $r$ steps. The existence of an $r$-forward-independent hitting set is equivalent to the existence of a Borel homomorphism from $G_f$ to $D_r$.
• Boundedness vs. Uniformity: They distinguish between bounded diameter and uniformly bounded diameter in equivalence relations, showing that for single-function graphs, these distinctions collapse in the context of asymptotic dimension.

5. Significance and Impact

1. Resolution of Complexity: The paper settles the complexity of finite Borel asymptotic dimension, proving it is maximally complex ($\Sigma^1_2$-complete). This provides a strong negative result regarding the possibility of simple dichotomy theorems for this class.
2. New Tool for Hyperfiniteness: By characterizing finite asymptotic dimension via hitting sets, the authors provide a new combinatorial tool to study Borel hyperfiniteness, potentially applicable to other open problems in the field.
3. Bridge Between Fields: The work creates a rigorous link between:
   • Descriptive Set Theory (complexity of sets of graphs).
   • Combinatorics (graph coloring, hitting sets).
   • Distributed Computing (LOCAL model complexity classes).
4. Counterexamples to Intuition: The result that $\text{asdim}_B(G_f) < \infty \implies \text{asdim}_B(G_f) = 1$ for single-function graphs contrasts with the behavior of general graphs, highlighting the unique structural constraints of functions.

6. Open Problems

The authors conclude with several open questions:

• Does the $\Sigma^1_2$-completeness result hold for bounded-degree Borel graphs (rather than just locally finite)?
• Is the graph generated by a commuting tuple of Borel functions hypersmooth? (They suggest asymptotic dimension might be a tool to tackle this).
• A refined characterization of the complexity of general Borel CSPs ($\text{CSP}_B(H)$) versus the function-generated subclass.

In summary, this paper is a significant contribution to descriptive set theory, establishing the high complexity of finite Borel asymptotic dimension and providing a deep combinatorial characterization that unifies concepts from graph theory, logic, and distributed computing.