{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q892143","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q892143","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q892143","kernelVersion":"v1","immutable":true,"modified":"2026-03-27T10:39:38Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q892143","name":"Ramsey-type graph coloring and diagonal non-computability","headline":"Ramsey-type graph coloring and diagonal non-computability","description":"scientific article; zbMATH DE number 6511007","url":"https://portal.mardi4nfdi.de/entity/Q892143","datePublished":"2015-11-18","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q490868"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q114337"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1007/S00153-015-0448-5","url":"https://doi.org/10.1007/S00153-015-0448-5"},"sameAs":["https://doi.org/10.1007/S00153-015-0448-5"],"comment":"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}].","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q5311768"},{"@id":"https://portal.mardi4nfdi.de/entity/Q515575"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3649154"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2795915"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3161424"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4899173"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2958212"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2869911"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3630585"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3478406"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2543461"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3489987"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3469096"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5363371"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1012969"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3758821"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5401600"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2892679"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3819052"}]},"provenance":{"prov:generatedAtTime":"2026-03-27T10:39:38Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}