R(n;r,s) vs R'(n;r,s) near Turán density equality

Informal Conjecture on R(n;r,s) vs R'(n;r,s) near Turán density · arXiv:2206.11371

arXiv Informal medium confidence— first stated 2022-06-22

Authors: David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques Verstraete

Status partial medium confidence

The informal conjecture that R(n;r,s) ≈ R'(n;r,s) when s/r is near the Turán density 1−1/(n−1) has not been explicitly resolved, but the same group of authors published a follow-up (arXiv:2305.14132) that studies R(n;r,s) precisely in the intermediate range where s/r is close to 1−1/(n−1) by connecting it to the maximum size of error-correcting codes near the zero-rate threshold — the same coding-theoretic quantity that defines R'. This provides partial progress towards the belief, but a precise comparison R(n;r,s) ≈ R'(n;r,s) has not been confirmed in the verified literature.

Cited literature (1)

partial Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold (2023)

David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques Verstraete · arXiv preprint · arXiv:2305.14132

Proves bounds on R(n;r,s) when s/r is close to the Turán density 1−1/(n−1) by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold, directly relevant to the regime where R and R' are conjectured to be close.

Reviewer notes. R'(n;r,s) is defined in the source paper as the minimum N such that every (r,s)-coloring of K_N yields a color class with chromatic number at least n; it equals A_{n-1}(r,s)+1 where A_{n-1}(r,s) is the maximum size of an (n−1)-ary error-correcting code of length r and distance r−s. The follow-up arXiv:2305.14132 connects R(n;r,s) to this same coding quantity in the Turán-density regime, constituting indirect partial evidence for the conjecture, but does not explicitly prove R≈R'. No paper was found that directly states and resolves this informal conjecture.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. We clearly have $R(n; r, s) \geq R'(n; r, s)$ and we believe that this estimate should be close to an equality when $s/r$ is close to the Turán density $1 - \frac{1}{n-1}$.

Context

The authors introduce the variant $R'(n;r,s)$, defined as the minimum $N$ such that every $(r,s)$-coloring of $K_N$ yields a color class with chromatic number at least $n$. They observe that $R(n;r,s) \geq R'(n;r,s)$ always holds, and that for the special case $s = r-1$ near-equality is confirmed by prior work of Alon et al. [1]. The informal belief is stated in Section 4 while studying the fixed-$n$ regime.

Notes. PDF source — math may be garbled. Statement reconstructed from prose; no labelled conjecture environment. The problems/further-remarks section mentioned at the end of the introduction is not present in the extracted text, so additional posed problems from that section may be missing.

Source paper

Set-coloring Ramsey numbers via codes
David Conlon, Jacob Fox, Xiaoyu He, Dhruv Mubayi, Andrew Suk, Jacques Verstraete · 2022-06-22
https://arxiv.org/abs/2206.11371 PDF source