Canonical Vertex Partitions
N. Sauer · Combinatorics Probability Computing · 2003
Let σ be a finite relational signature, let be a set of finite complete relational structures of signature σ, and let be the countable homogeneous relational structure of signature σ which does not embed any of the structures in . When σ consists of at most binary relations and is finite, the vertex partition behaviour of is completely analysed, in the sense that it is shown that a canonical partition exists and the size of this partition in terms of the structures in is determined. If is infinite some results are obtained, but a complete analysis is still missing. Some general results are presented which are intended to be used in further investigations when σ contains relational symbols of arity larger than two or when the set of bounds is infinite.