← All problems

Erdős's lower-bound conjecture for off-diagonal Ramsey numbers

1 year old · traced to

Let r(s,t)r(s,t) denote the minimum integer nn such that every red-blue coloring of the edges of the complete graph on nn vertices contains a red copy of KsK_s or a blue copy of KtK_t. Erdős's conjecture. For all s≥4s \geq 4, there exists c=c(s)>0c=c(s)>0 such that

r(s,t)≥ts−1(log⁡t)c.r(s,t) \geq \frac{t^{s-1}}{(\log t)^c}.

This conjecture predicts the expected polynomial order of off-diagonal Ramsey numbers up to a power of a logarithm. The paper notes that the case s=4s=4 is resolved by the stated bounds for r(4,t)r(4,t), while the general case remains open.

References
  1. Jacques Verstraete, “Recent Progress in Ramsey Theory”, arXiv:2503.22094 (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 2

Claimed by OpenAI. The manuscript claims r(5,t)=t^4/(log t)^(3+o(1)) as t tends to infinity. In particular, for every fixed c>3 this yields the page’s lower bound r(5,t)>=t^4/(log t)^c for all sufficiently large t. This addresses the s=5 case and its logarithmic exponent; it does not establish other fixed clique sizes or a sharp multiplicative constant.See full solutionHide full solution
Claimed by OpenAI. For every fixed s>=6, the manuscript claims r(s,t)=t^(s-1)/(log t)^(s-2+o(1)) as t tends to infinity. Thus every fixed c(s)>s-2 gives the page’s requested lower bound for sufficiently large t. This addresses those fixed clique sizes and their logarithmic exponents; uniform growth in s, the cases s=4 or s=5, and sharp multiplicative constants are not claimed in this manuscript.See full solutionHide full solution