Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 23 / 6

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.

An exact-count form of the Hanf locality lemma is as follows. For every quantifier rank $q$, put $r=3^q$. If finite relational structures $A,B$ admit a bijection $f:A\to B$ such thatthen $A$ and $B$ agree on every first-order sentence of quantifier rank at most $q$. Equivalently, they have the same number of occurrences of every marked radius-$r$ one-point neighbourhood type. The individual local isomorphisms need not be restrictions of $f$.

A bounded-degree threshold version permits the type counts to be different when both exceed a sufficiently large bound depending on the degree bound and $q$. We need only the exact-count form. Its locality content is that sufficiently large matching neighbourhoods and their multiplicities determine all sentences up to the prescribed quantifier rank.

Suppose a first-order sentence $\theta$ defined the bipartite graphs, equivalently the 2-colourable graphs. Let $q$ be its quantifier rank and $r=3^q$. Choose an odd integer $N>2r+1$, and compareBoth have $2N$ vertices. Every marked radius-$r$ neighbourhood in either graph is a path with $2r+1$ vertices and its middle vertex marked: the choice of $N$ prevents the ball from wrapping around a cycle. Thus every vertex has exactly the same neighbourhood type in both graphs, and that type occurs $2N$ times in each. Any bijection of their universes meets the Hanf locality lemma hypothesis.

Therefore $A$ and $B$ agree on $\theta$. But $A$ is an even cycle and is bipartite, whereas $B$ contains odd cycles and is not bipartite. This contradiction provesThe equal total size is useful here: no large-count threshold or comparison of unequal multiplicities is needed.