Ramsey-type graph coloring and diagonal non-computability (Q892143): Difference between revisions

For each computable function \(h\), the author uses bushy tree forcing to construct an \(\omega\)-model of RCA\(_0\)+\(h\)-DNR that is not a model of RCOLOR\(_2\). The principle \(h\)-DNR asserts the existence of an \(h\)-bounded d.n.c. function. Given a graph \(G\) with vertices \(V\), a set \(H \subseteq V\) is \(k\)-homogeneous if for every finite \(V_0\subseteq V\) there is a \(k\)-coloring of the vertices of \(G\) restricted to \(V_0\) that is monochromatic on \(V_0 \cap H\). The principle RCOLOR\(_k\) asserts that every locally \(k\)-colorable graph has an infinite \(k\)-homogeneous set. For \(k\geq 3\), RCOLOR\(_k\) is equivalent to RWKL, as shown by \textit{L. Bienvenue}, \textit{L. Patey}, and \textit{P. Shafer} [``On the logical strengths of partial solutions to mathematical problems'', Preprint, \url{arXiv:1411.5874}]. Clearly, RCOLOR\(_2\) is weaker than RCOLOR\(_3\), but it is not known if this relationship is strict. The results of the paper address a question of \textit{S. Flood} and \textit{H. Towsner} [``Separating principles below WKl\(_0\)'', Preprint, \url{arXiv:1410.4068}].