The Henson graphs: colorings and codings

Abstract

By recent work of \citet{DobrinenICM} and \citet{Balko7} we know that every finite $G$ in the Henson graph ${\mathbb{H}}_{n+1}$ (the universal ultrahomogeneous $(n+1)$-clique free graph) has exact finite big Ramsey degree $k(G,n)$. That is, there is a positive integer $k(G,n)$ such that for each finite coloring $C$ of the copies of $G$ in ${\mathbb{H}}_{n+1}$, there is $\tilde{\mathbb{H}}$, a substructure of ${\mathbb{H}}_{n+1}$ and isomorphic to ${\mathbb{H}}_{n+1}$, such that in $\tilde{\mathbb{H}}$ at most $k(G,n)$ colors are used on the copies of $G$ in $\tilde{\mathbb{H}}$. Moreover, for exactness, for some coloring and all corresponding $\tilde{\mathbb{H}}$, all $k(G,n)$ colors are needed. The ultimate result here is that if $|G|\ge 2$, then there is a finite computable coloring $C$ such that, for all such $\tilde{\mathbb{H}}$, we have that $\tilde{\mathbb{H}}$ computes ${\varnothing }^{(|G|-1)}$ (and hence the halting set).

Minor changes