Erdős's lower-bound conjecture for off-diagonal Ramsey numbers
Let denote the minimum integer such that every red-blue coloring of the edges of the complete graph on vertices contains a red copy of or a blue copy of . Erdős's conjecture. For all , there exists such that
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 is resolved by the stated bounds for , while the general case remains open.
References
- 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 solution
GitHub repository: https://github.com/openai/math
- OpenAI-170-01-The-sharp-logarithmic-exponent-of-r-5-t.pdfOpen
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 solution
GitHub repository: https://github.com/openai/math
- OpenAI-170-02-Sharp-logarithmic-exponents-for-fixed-off-diagonal-Ramsey-numbers.pdfOpen