Asymptotic constant for the off-diagonal Ramsey numbers R(3,k)

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.

Current state (tracked automatically)

Best known bounds for constant 17b: 0.5 ≤ C ≤ 1. Upper bound ([She1983], Via Shearer's lower bound on the independence number of triangle-free graphs in terms of the average degree); lower bound ([HHKP2025]).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 17b)	0.5 [HHKP2025]	Tao's optimization constants
Best upper bound with an explicit value (constant 17b)	1 [She1983] — Via Shearer's lower bound on the independence number of triangle-free graphs in terms of the average degree	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-constant-17b-asymptotic-constant-for-the-off-diagonal-ramsey-numbers-r-3-k,
  title        = {Asymptotic constant for the off-diagonal Ramsey numbers R(3,k)},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-17b-asymptotic-constant-for-the-off-diagonal-ramsey-numbers-r-3-k}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-17b-asymptotic-constant-for-the-off-diagonal-ramsey-numbers-r-3-k.json)](https://cairn-commons.com/problems/constant-17b-asymptotic-constant-for-the-off-diagonal-ramsey-numbers-r-3-k)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

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} / lo g k$ [AKS1980], [Kim1995]. Define

$C_{17 b} := k \to \infty lim \frac{R ( 3 , k )}{k ^{2} / lo g k},$

if the limit exists, where $lo g$ is the natural logarithm.

Known upper bounds

Bound	Reference	Comments
$< \infty$	[AKS1980]	First upper bound of the correct order $O (k^{2} / lo g 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} / lo g^{2} k$ , one logarithm short of the correct order
$> 0$	[Kim1995]	First lower bound of the correct order $Ω (k^{2} / lo g 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_{17 b}$ should be interpreted as bounding the limit superior (resp. limit inferior).
Determining $C_{17 b}$ 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 $Z_{240}$ gives $R (3, 33) \geq 241$ [SK2026]. Bounds for individual small $k$ do not bear directly on $C_{17 b}$ .

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} / lo g 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

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.