= Solution
For a relational <first-order structure> $A$, form its <Gaifman graph>: distinct elements are adjacent when they occur together in a tuple of some interpreted relation. Let $d_A$ be graph distance, with distance infinite between different components. For a tuple $\mathbf a=(a_1,\ldots,a_m)$, its radius-$r$ neighbourhood has universe
$$
N_r^A(\mathbf a)=\{b\in A:\min_i d_A(b,a_i)\le r\}.
$$
The neighbourhood structure is the induced relational structure on this set, expanded by constants marking the entries of $\mathbf a$ in their original order. Its isomorphism type thus records the centres, not just the unmarked ball. For one binary graph relation, this is the usual union of the radius-$r$ graph balls. This formulation assumes the finite relational signatures used in the finite-model setting.
Back to article page
