University of Calgary

# Canonical partitions of universal structures

## Abstract

Let $\mathbb{U}=(U,\mathfrak{L})$ be a universal binary countable homogeneous structure and $n\in \omega$. We determine the equivalence relation $\mathcal{C}(n)(\mathbb{U})$ on $[U]^n$ with the smallest number of equivalence classes $r$ so that each one of the classes is indivisible. As a consequence we obtain $\mathbb{U}\to (\mathbb{U})^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\H{o}s and Rado for the integers to countable universal binary homogeneous structures.