Asymptotic constant for the off-diagonal Ramsey numbers $R(3,k)$
Description of constant
Let $R(3,k)$ be the smallest integer $n$ such that every red/blue colouring of the edges of the complete graph $K_n$ contains a red triangle or a blue $K_k$. Equivalently, $R(3,k)-1$ is the largest number of vertices of a triangle-free graph with independence number less than $k$. It is known that $R(3,k)$ has order of magnitude $k^2/\log k$ [AKS1980], [Kim1995]. Define
\[C_{17b} := \lim_{k \to \infty} \frac{R(3,k)}{k^2/\log k},\]if the limit exists, where $\log$ is the natural logarithm.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $<\infty$ | [AKS1980] | First upper bound of the correct order $O(k^2/\log k)$ |
| $1$ | [She1983] | Via Shearer’s lower bound on the independence number of triangle-free graphs in terms of the average degree |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $0$ | [Erd1961] | Proves $R(3,k) \geq c k^2/\log^2 k$, one logarithm short of the correct order |
| $>0$ | [Kim1995] | First lower bound of the correct order $\Omega(k^2/\log k)$, via a semi-random construction |
| $\frac{1}{4}$ | [BK2021], [FGM2020] | Independent analyses of the triangle-free process (preprints from 2013) |
| $\frac{1}{3}$ | [CJMS2025] | Also disproves the conjecture of [FGM2020] that $\frac{1}{4}$ is sharp |
| $\frac{1}{2}$ | [HHKP2025] |
Additional comments and links
- The existence of the limit is open. For the purposes of this page, upper (resp. lower) bounds on $C_{17b}$ should be interpreted as bounding the limit superior (resp. limit inferior).
- Determining $C_{17b}$ is Erdős problem #165.
- The value $\frac{1}{2}$ has been conjectured to be the correct constant by several groups; see [CJMS2025] and [HHKP2025].
- See $C_{17}$ for the diagonal Ramsey numbers.
- Small values. Exact values of $R(3,k)$ are known only for $k \leq 9$; see the dynamic survey [Rad] for the current small-$k$ bounds. Recent computer searches over circulant graphs give improved lower bounds for $24 \leq k \leq 49$ [CFLSTT2026], and a circulant graph on $\mathbb{Z}_{240}$ gives $R(3,33) \geq 241$ [SK2026]. Bounds for individual small $k$ do not bear directly on $C_{17b}$.
References
- [AKS1980] Ajtai, M.; Komlós, J.; Szemerédi, E. A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), 354–360.
- [BK2021] Bohman, T.; Keevash, P. Dynamic concentration of the triangle-free process. Random Structures Algorithms 58 (2021), 221–293. arXiv:1302.5963
- [CFLSTT2026] Coniglio, S.; Furini, F.; Ljubić, I.; San Segundo, P.; Thüerauf, J.; Traversi, E. An integer programming approach to compute lower bounds for Ramsey numbers using circulant graphs. arXiv:2608.18769 (2026).
- [CJMS2025] Campos, M.; Jenssen, M.; Michelen, M.; Sahasrabudhe, J. A new lower bound for the Ramsey numbers $R(3,k)$. arXiv:2505.13371 (2025).
- [Erd1961] Erdős, P. Graph theory and probability. II. Canad. J. Math. 13 (1961), 346–352.
- [FGM2020] Fiz Pontiveros, G.; Griffiths, S.; Morris, R. The triangle-free process and the Ramsey number $R(3,k)$. Mem. Amer. Math. Soc. 263 (2020), no. 1274. arXiv:1302.6279
- [HHKP2025] Hefty, Z.; Horn, P.; King, D.; Pfender, F. Improving $R(3,k)$ in just two bites. arXiv:2510.19718 (2025).
- [Kim1995] Kim, J. H. The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$. Random Structures Algorithms 7 (1995), 173–207.
- [Rad] Radziszowski, S. P. Small Ramsey numbers. Electron. J. Combin., Dynamic Survey DS1.
- [She1983] Shearer, J. B. A note on the independence number of triangle-free graphs. Discrete Math. 46 (1983), 83–87.
- [SK2026] Suresh Kannan, S. A circulant Ramsey (3,33)-graph on 240 vertices: R(3,33) >= 241 and R(3,34) >= 244. Zenodo (2026). doi:10.5281/zenodo.23552014
Contribution notes
Claude Code (Anthropic) was used to prepare an initial version of this page. The bounds for [CJMS2025] and [HHKP2025] were checked against their arXiv abstracts, and the problem statement against Erdős problem #165. The contributor is the author of [SK2026].