What does local mean?

My work on local-global structure theory starts with what “local” means. The purpose of this short post is to flesh out this definition.

First, we fix a parameter $r \geq 1$. This parameter represents the scale of locality; picture zooming in or out depending on how much information we want to consider “local.” Now, for a graph $G$ and a vertex $v \in V(G)$, the ball of radius $r/2$ around $v$, denoted $B_G(v, r/2)$, is the subgraph of $G$ with:

• vertex set the set of all vertices of distance at most $\lfloor r/2 \rfloor$ from $v$; and
• edge set the set of all edges $uw$ with such that $d(u, v) + d(w, v) < r$.

Let’s think through why we want to go to the trouble of defining balls with half-integral radii, instead of using more familiar notions such as, say, bounded-depth neighborhoods.

First, observe that for odd values of $r$, the balls above do correspond to bounded-depth neighborhoods; namely: \(B_G(v, r/2) = N^{\lfloor r/2 \rfloor}[v].\)

Let’s fix a vertex $v$ and look at what happens when we grow $r$.

• $B_G(v, 1/2)$ is simply the vertex $v$.
• $B_G(v, 2/2)$ consists of $v$, the neighbors of $v$, and the edges from $v$ to its neighbors, but no edges between neighbors of $v$.
• $B_G(v, 3/2)$ consists of $v$, the neighbors of $v$, the edges from $v$ to its neighbors, and the edges between neighbors of $v$.
• $B_G(v, 4/2)$ adds the next layer of vertices — those with neighbors in $B_G(v, 3/2)$ and the edges to those neighbors in $B_G(v, 3/2)$, but no edges between them.
• $B_G(v, 5/2)$ adds the edges between the vertices added in the previous step.
• And so on… $B_G(v, r/2)$ builds from $B_G(v, (r-1)/2)$ by adding the next layer of vertices, if $r$ is even, and by adding the next layer of edges, if $r$ is odd.

You can see that this is a more precise way of growing balls than simply relying on closed neighborhoods. This is advantageous for two reasons. First, the definition was chosen to mimic the definition of a metric ball. We can use this analogy to see why $B_G(v, 2/2)$ (with $r=2$) does not contain edges between neighbors of $v$. Consider the midpoint of such an edge. To walk from this midpoint to $v$ and back requires a distance of $3$, not $2$.

Second, the $r/2$-balls give us the precision to tell the difference between cycles whose lengths differ by one. For example, consider $C_4$ and $C_5$.

• Both $C_4$ and $C_5$ are not contained in the neighborhood $N[v]$ for any of their vertices $v$.
• Both $C_4$ and $C_5$ are contained in the second neighborhood $N^2[v]$ for all of their vertices $v$.
• $C_4$ is contained in $B_{C_4}(v, 4/2)$ for all of its vertices .
• $C_5$ is not contained in $B_{C_5}(v, 4/2)$ for any of its vertices $v$.
• $C_5$ is contained in $B_{C_5}(v, 5/2)$ for all of its vertices $v$.

As we can see, bounded-depth closed neighborhoods cannot distinguish between $C_4$ and . But the radius $4/2$-balls tell us that $C_4$ is “more local” than $C_5$. And, appealingly, the cycle $C_\ell$ is contained in $B_{C_\ell}(v, r/2)$ if and only if $r \geq \ell$.

Now that we have convinced ourselves that the $r/2$-ball definition is nice, we can fix the following definition:

The $r$-local pieces of $G$ are the radius $r/2$-balls of $G$.

What does this look like in practice? One thing we can do with this definition is use it to define when a graph is “locally X.” For example:

A graph $G$ is $r$-locally acyclic if every ball of radius $r/2$ in $G$ is acyclic.

Or:

A graph $G$ is $r$-locally chordal if every ball of radius $r/2$ in $G$ is chordal.

In this way, $r/2$-balls formalize what we mean by “the local structure of a graph.”