University of Calgary

Coloring subgraphs of the Rado graph

Abstract

Given a universal binary countable homogeneous structure $U$ and $n\in \omega$, there is a partition of the induced $n$-element substructures of $U$ into finitely many classes so that for any partition $C_0,C_1,\dots, C_{m-1}$ of such a class $Q$ into finitely many parts there is a number $k\in m$ and a copy $U^\ast$ of $U$ in $U$ so that all of the induced $n$-element substructures of $U^\ast$ which are in $Q$ are also in $C_k$. The partition of the induced $n$-element substructures of $U$ is explicitly given and a somewhat sharper result as the one stated above is proven.
Powered by UNITIS. More features.