Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 23 / 6 / a / 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,\dots ,a_m)$, its radius-$r$ neighbourhood has universeThe 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.