Canonical Partitions Of Universal Structures

Let ${\Bbb U}{\left( {U,\pounds } \right)}$ be a universal binary countable homogeneous structure and n∈ω. We determine the equivalence relation $C{\left( n \right)}{\left( {\Bbb U} \right)}$ on [U]ⁿ with the smallest number of equivalence classes r so that each one of the classes is indivisible. As a consequence we obtain

$$ {\Bbb U} \to {\left( {\Bbb U} \right)}^{n}_{{ < \omega /r}} $$

and a characterization of the smallest number r so that the arrow relation above holds.

For the case of infinitely many colors we determine the canonical set of equivalence relations, extending the result of Erdős and Rado for the integers to countable universal binary homogeneous structures.