Nonreducibility conjectures for cohesive and stable Ramsey principles

From papers

Let COH\mathsf{COH} denote the cohesive principle, let IndEk\operatorname{\mathsf{Ind}}\mathscr{E}_k denote the indicated indivisibility problem for kk-colorings, and let c\leq_{\mathrm{c}} denote the relevant computable reducibility. Write N\mathbb{N} for the set of natural numbers. Nonreducibility conjecture.

COH̸cIndEN\mathsf{COH} \not\leq_{\mathrm{c}} \operatorname{\mathsf{Ind}}\mathscr{E}_{\mathbb{N}}

and

IndE2̸cSRTN2,\operatorname{\mathsf{Ind}}\mathscr{E}_2 \not\leq_{\mathrm{c}} \mathsf{SRT}^2_{\mathbb{N}},

or, at least,

IndEk̸cSRTk2.\operatorname{\mathsf{Ind}}\mathscr{E}_k \not\leq_{\mathrm{c}} \mathsf{SRT}^2_k.

The conjecture concerns the open separation of the indivisibility principles from cohesive and stable Ramsey principles under computable reducibility; the source presents these nonreducibilities as conjectural after noting that the corresponding reducibility questions are open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Kenneth Gill, “Indivisibility and uniform computational strength”, arXiv:2312.03919 (2025).

Solutions 0

No solutions have been posted yet.