Nonreducibility conjectures for cohesive and stable Ramsey principles

About 3 years old · traced to

Let COH\mathsf{COH} denote the cohesive principle, let Ind⁡Ek\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̸≤cInd⁡EN\mathsf{COH} \not\leq_{\mathrm{c}} \operatorname{\mathsf{Ind}}\mathscr{E}_{\mathbb{N}}

and

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

or, at least,

Ind⁡Ek̸≤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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.