For a relational structure, the Gaifman graph has the same universe. Two distinct elements are adjacent if they occur together in some tuple of some interpreted relation. A tuple's radius- neighbourhood is the induced structure on the union of its radius- graph balls, with the tuple marked by constants.
For a finite relational signature and quantifier rank , matching the numbers of all marked radius- one-point neighbourhood types suffices for two finite structures to satisfy the same first-order sentences of rank at most . Equivalently, a bijection can match the isomorphism types of these marked neighbourhoods point by point. On bounded-degree structures, a threshold version permits large neighbourhood-type counts to differ once both exceed a fixed bound. Long cycles of equal total size give useful exact-count applications.
Articles by others on the same topic
There are currently no matching articles.