Abstrakt
An ultrahomogeneous structure is a (finite or countable) relational structure for which every partial isomorphism between finite substructures can be extended to a global isomorphism. This very strong symmetry condition implies that there are just a few ultrahomogeneous structures.
For example, by [14], there are just countably many ultrahomogeneous undirected graphs. The classification program is one of the celebrated lines of research in the model theory, see [4, 15].
Various measures were introduced in order to modify a structure to an ultrahomogeneous one. A particularly interesting measure is the minimal arity of added relations (i.e. the minimal arity of an extension or lift) which suffice to produce an ultrahomogeneous structure.
If these added relations are not changing the automorphism group then the problem is called the relational complexity and this is the subject of this paper. In the context of permutation groups, the relational complexity was defined in [5] and was recently popularized by Cherlin [2,3].
We determine the relational complexity of one of the most natural class of structures (the class of structures defined by forbidden homomorphisms). This class has a (countably) universal structure [6].
As a consequence of our main result (Theorem 3.1) we strengthen this by determining its relational complexity. Although formulated in the context of model theory this result has a combinatorial character.
Full details will appear in [9]