An asymptotic formula for the Ramsey number R(3,k)

How many vertices force a triangle-free graph to contain an independent set of size $k$? This Ramsey number $R(3,k)$ is known to be of order $k^2/\log k$, and since 2025 the lower and upper bounds differ only by a factor of $2$. Erdős asked for the exact asymptotics.

Problem

Let $R(3,k)$ be the least $n$ such that every graph on $n$ vertices contains either a triangle or an independent set of $k$ vertices. Find an asymptotic formula for $R(3,k)$; that is, determine the constant $c$ (if it exists) with

$$R(3,k)=(c+o(1))\frac{k^2}{\log k}.$$

Erdős offered $250 for this problem.

Background

Determining even the order of magnitude of $R(3,k)$ took decades: Ajtai, Komlós and Szemerédi (1980) proved the upper bound $O(k^2/\log k)$, and Kim (1995) proved a matching lower bound. Upper bounds come from lower bounds on the independence number of triangle-free graphs: Shearer showed that a triangle-free graph on $n$ vertices with average degree $d$ has an independent set of size at least $(1+o(1))\,n\log d/d$. Lower bounds come from random constructions of triangle-free graphs, such as the triangle-free process, which adds random edges one at a time as long as no triangle is created.

What is known

• Upper bound. Shearer (1983) proved $R(3,k)\le(1+o(1))k^2/\log k$, improving the constant of Ajtai, Komlós and Szemerédi; it is still the best upper bound.
• Lower bounds. Kim (1995) proved $R(3,k)\ge(c+o(1))k^2/\log k$ with $c=1/162$. The analysis of the triangle-free process by Bohman and Keevash (2021) and, independently, Fiz Pontiveros, Griffiths and Morris (2020) gave $c=1/4$; the latter conjectured that $1/4$ is sharp. Campos, Jenssen, Michelen and Sahasrabudhe (2025) disproved this with $c=1/3$, and Hefty, Horn, King and Pfender (2025) reached $c=1/2$.
• Both 2025 papers conjecture that $1/2$ is the correct constant, so the conjectured formula is $R(3,k)\sim k^2/(2\log k)$. The proof of the $1/2$ bound has since been formalised in Lean (formalisation, 2026).

What would count as progress

• An upper bound $R(3,k)\le(1-\varepsilon+o(1))k^2/\log k$ for some fixed $\varepsilon>0$, the first improvement on Shearer's bound.
• A lower bound with a constant above $1/2$, which would refute the current conjecture; constructions can be tested on moderate $k$ by computing independence numbers.
• A matching upper and lower bound, which would solve the problem.

References

1. M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), 354–360. doi:10.1016/0097-3165(80)90030-8
2. J. B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), 83–87. doi:10.1016/0012-365X(83)90273-X
3. J. H. Kim, The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$, Random Structures Algorithms 7 (1995), 173–207. doi:10.1002/rsa.3240070302
4. T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process, Random Structures Algorithms 58 (2021), 221–293. doi:10.1002/rsa.20973
5. M. Campos, M. Jenssen, M. Michelen and J. Sahasrabudhe, A new lower bound for the Ramsey numbers $R(3,k)$ (2025). arXiv:2505.13371
6. Z. Hefty, P. Horn, D. King and F. Pfender, Improving $R(3,k)$ in just two bites (2025). arXiv:2510.19718

Source

Imported from Erdős Problems 165, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.